p-value<2e−16 p-value=2e−16 p-value=2e−16 WT (00-05min: 857.268 ± 47.476; 05-10min: 771.542 ± 61.456; 10-15min: 684.255 ± 67.006; 15-20min: 672.084 ± 81.929; 20-25min: 545.335 ± 72.849; 25-30min: 504.946 ± 73.010; 30-35min: 453.953 ± 70.695; 35-40min: 458.555 ± 58.926; 40-45min: 379.933 ± 64.480; 45-50min: 300.615 ± 66.047; 50-55min: 348.369 ± 67.830; 55-60min: 398.494 ± 57.834; n=10; _mean ± S.E.M_). 50% & p < 0.5 p > 0.5 >

Consider ternary strings, that is strings formed from symbols 0, 1, and 2. Let Zn be the number of ternary strings of length n that do not contain substrings 22 and 12. For example, for n = 3, all the strings with this property are: 000, 001, 002, 010, 011, 020, 021, 100, 101, 102, 110, 111, 200, 201, 202, 210, 211, and thus Z₃ = 17. (Note that Z₀ = 1, because the empty string satisfies the condition.) (a) Derive a recurrence relation for the numbers Zn. Justify it. (b) Find the formula for the numbers Zn by solving this recurrence. Show your work. SOLUTION 1: (a) Z₀ = 1 Z₁ = 3  {1, 2, 3} Z₂ = 7  {00, 01, 02, 10, 11, 20, 21} Z₃ = 17 To compute the recurrence, we can look at the possible endings for the strings. In the event that the string ends with a 0 or 1, any other number can precede this instance. Giving us 2 * Zn − 1. However, if the string ends with 2, the number preceding it must be 0, since we cannot have the sequence 12 or 22. This gives us Zn − 2 Graphically this can be represented as: * * * * 0   +    * * * *1   +    * * * 02 Where * represents any number of digits in a string of Z Therefore, the recurrence relation is Zn = 2 * Zn − 1 + Zn − 2 (b) Finding the characteristic equation, we get: x² − 2x − 1 = 0 To find the roots, we use the quadratic equation. $}{2}$ and $}{2}$ $}{2}$ and $}{2}$ $x = 1+$, $1-$ The general form can be represented as: $Z_n = \alpha _1 (1+)^n + \alpha _2 (1-)^n$ Now, we solve for the initial conditions For $n=0 \: \: \: \alpha _1 (1+)^0 + \alpha _2 (1-)^0 = 1$ α₁ + α₂ = 1 α₁ = 1 − α₂ For $n=1 \: \: \: \alpha _1 (1+)^1 + \alpha _2 (1-)^1 = 3$ $(1-\alpha _2)(1+) + (\alpha _2)(1-) = 3$ $1-\alpha _2 + -\alpha _2 + \alpha _2 \ \alpha _2 = 3$ $1+-2\alpha _2 = 3$ $-2\alpha _2 = 2$ $-2\alpha _2 = 2 -$ $\alpha _2 = }{-2}$ $\alpha _1 = 1 - }{-2}$ $Z_n = (1 - }{-2})(1+)^n + (}{-2})(1-)^n$ Solve the following recurrence equation: V_n &=& V_{n-1} + 3V_{n-2} + V_{n-3} + 2n\\ V_0 &=& 0 \\ V_1 &=& 0 \\ V_2 &=& 1 Show your work (all steps: the associated homogeneous equation, the characteristic polynomial and its roots, the general solution of the homogeneous equation, computing a particular solution, the general solution of the non-homogeneous equation, using the initial conditions to compute the final solution.) SOLUTION 2: First, we will find the homogeneous variant x³ − x² − 3x − 1 = 0 Plugging in a few roots, we find that x = −1 is a root. Using long division ${x+1}$ We get a quadratic equation x² − 2x − 1 Then, we solve for the roots of this equation using the quadratic formula and get: $x=-1, \: 1+, \: 1-$ General solution: $v^{'}_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n$ Particular solution: $v_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n + \beta$ Now, we will solve for β $V^{"}_n = \beta _1 n + \beta _2$ β₁n + β₂ = (β₁(n − 1)+β₂)+3(β₁(n − 2)+β₂)+(β₁(n − 3)+β₂)+2n 5β₁n − 10β₁ + 5β₂ + 2n (5β₂ + 2)n + (5β₂ − 10β₁)=0 For n = 0 5β₂ − 10β₁ = 0 β₂ = 2β₁ 5β₁ + 2 + 10β₁ − 10β₁ = 0 5β₁ = −2 $\beta _1 = -{5}$ $\beta _2 = -{5}$ $V^{"}_n = -{5}n - {5}$ General solution: $v_n = \alpha _1 (-1)^n + \alpha _2 (1+)^n + \alpha _3 (1-)^n -{5}n - {5}$ Initial conditions: n = 0 $\alpha _1 = {5}-\alpha _2 - \alpha _3$ n = 1 $-\alpha _1 + (1+)\alpha _2 + (1-)\alpha _3 = {5}$ n = 2 $\alpha _1 + \alpha _2(3+2)+\alpha _3(3-2) = {5}$ $\alpha _1 = -{5}-{5}-{5}+{5})+({5}+{5})}{2+}$ $\alpha _2 = {5}+{5})+({5}+{5})}{2+}$ $\alpha _3 = {5}+{5}$ The solution is: $V_n = (-{5}-{5}-{5}+{5})+({5}+{5})}{2+})(-1)^n+{5}+{5})+({5}+{5})}{2+}(1+)^n+{5}+{5}(1-)^n-{5}n - {5}$ To submit the homework, you need to upload the pdf file into ilearn by 8AM on Tuesday, May 13, and turn-in a paper copy in class.

PROBLEM 1: Let x be a positive integer and y = x² + 2. Can x and y be both prime? The answer is yes, since for x = 3 we get y = 11, and both numbers are prime. Prove that this is the only value of x for which both x and y are prime. _Hint:_ Consider cases, depending on the remainder of x modulo 3. SOLUTION 1: If x ≠ 3, then x = 1 or x = 2 in x modulo 3. x = 1 and x = 2 would be prime under the equation x² = 1 (mod 3) However, with the equation x² + 2, both x = 1 and x = 2 result in 0 x² + 2 = 0(mod 3) This means that 3 evenly divides into x² + 2 for x = 1 and x = 2, meaning that y is not prime for both of these terms. Additionally, y ≠ 3 because the equation is only true for x = 1 and 1 is not a prime number. Therefore, since for x = 1 and x = 2, y is divisible by 3 and y ≠ 3, the only case where both x and y can be prime is x = 3

__ PROBLEM 1: (a) You are eagerly waiting for the delivery of your smart phone. For each day the delivery is late, the phone company compensates you by giving you coupons. The number of coupons you get for each day is equal to the number of days the delivery is late. For example, if your phone is late 2 days, you get 1 coupon for the first day and 2 coupons for the second day. Use a summation notation ∑ to give the formula for the total number of coupons received in the first k days after the delivery was due. Then give a closed-form formula (without the ∑ symbol) for this number. (b) The coupons turn out to be more valuable than you thought. Each coupon is worth $1 the day you receive it, but since then its value doubles after each day. For example, if the phone is late 3 days, the coupon for the first day will be now worth $4, each of the two coupons for the second day will be worth $2, while the three coupons for the third day will be worth $1. Let W(n) be the total value of coupons collected if the delivery was n days late. Give the formula (using the summation notation) for W(n). (c) Derive a closed-form expression for W(n). (d) Finally, give the asymptotic value of W(n) using the Θ-notation. Include a brief justification for each step. If you need any summation formulas for this problem, you are allowed to look them up. SOLUTION 1: (a) Since we are receiving one extra coupon for each consecutive day: 1 + 2 + … + (k − 1)+k, the total coupons received for k days can be represented as $\sum^k i$ = ${2}$ (b) Since we are still receiving one extra coupon for each consecutive day, $\sum^n i$ can still represent the number of coupons received. However, the value of the coupons is: 1 + 2 + 4 + … + (n − 1)+2(n − 1) which can be represented as $\sum^n 2^{n-i}$. We must multiply the quantity and the value together during each sum to get the total value resulting in: $W(n) = \sum^n i*2^{n-i}$ (c) For n = 1 through n = 6, - W(1)=1 - W(2)=4 - W(3)=11 - W(4)=26 - W(5)=57 We know that the closed form expression should involve a value slightly larger than 2n, so we try the same n values for 2n + 1 and get: - 21 + 1 = 4 - 22 + 1 = 8 - 23 + 1 = 16 - 24 + 1 = 32 - 25 + 1 = 64 The difference between 2n + 1 and W(n) appears to be −n − 2 for each term, so the closed form expression for W(n) must be $\sum^n i*2^{n-i} = 2^{n+1}-n-2$. We can prove that this expression is correct using induction. PROOF: Base Case: For W(1), 21 + 1 − 1 − 2 = 1 which is correct since W(1)=1. Assume W(k)=2k + 1 − k − 2, we must show that W(k + 1)=2k + 2 − k − 3 Based off of the sequence W(n) - W(1)=1 - W(2)=4 - W(3)=11 - W(4)=26 - W(5)=57 We see that each term W(k + 1)=2W(k)+(k + 1) so, W(k + 1)=2(2k + 1 − k − 2)+(k + 1) W(k + 1)=2k + 2 − 2k − 4 + k + 1 W(k + 1)=2k + 2 − k − 3 Therefore, W(n)=2n + 1 − n − 2 _Q.E.D._ (d) First, we will find the lower bound for W(n)=2n + 1 − n − 2 After removing constants, we find that $2^{n}-n \geq 2^n - {2}$ which is true for n > 2 Since $2^n-{2}$ belongs to Ω(2n), W(n) must as well since it is greater than or equal to $2^n-{2}$ Now we will find the upper bound for W(n)=2n + 1 − n − 2 After removing constants, 2n − n ≤ 2n, therefore, W(n) belongs to O(2n) Since W(n) belongs to both Ω(2n) and O(2n), W(n)=θ(2n) PROBLEM 2: Prove that there is an integer c > 0 such that the following inequality holds for all n ≥ c: 2^n + 3^n +4^n \le 5^n. Then explain how this implies that 2n + 3n + 4n = O(5n). Hint: By hand, find the smallest c for which n = c satisfies this inequality, and then prove by induction that it holds for all n ≥ c. SOLUTION 2: Base Case: For n = 3 2³ + 3³ + 4³ ≤ 5³ 99 ≤ 125, so the inequality is true for n = 3 Assume 2k + 3k + 4k ≤ 5k, we must show that 2k + 1 + 3k + 1 + 4k + 1 ≤ 5k + 1 2k + 3k + 4k ≤ 5k First, we multiply both sides by 5 5(2k + 3k + 4k)≤5 * 5k 5 * 2k + 5 * 3k + 5 * 4k ≤ 5 * 5k We can replace each 5 with the value of the coefficient for each term. This still keeps the inequality true. 2 * 2k + 3 * 3k + 4 * 4k ≤ 5 * 5k 2k + 1 + 3k + 1 + 4k + 1 ≤ 5k + 1 Therefore, the inequality must hold for n ≥ c, where c = 3 _Q.E.D_ This implies that 2n + 3n + 4n = O(5n) because for n ≥ c, 2n + 3n + 4n is bounded by and never exceeds 5n. Therefore, 2n + 3n + 4n = O(5n).