CMSC250, Spring 2004 Homework 7 AnswersDue Wednesday, March 17 at the beginning of your discussion section.You must write the solutions to the problems single-sided on your own lined paper,with all sheets stapled together, and with all answers written in sequential order oryou will lose points.1. Simplify this expression: ln"nYi=1ef(i)#.Answer:ln"nYi=1ef(i)#= lnhef(1)· ef(2)···ef(n)i= ln ef(1)+ ln ef(2)+ ··· + ln ef(n)= f(1) + f(2) + ··· + f(n)=nXi=1f(i)2. Prove ∀n ∈ Z+nXi=1(2i)(2i − 1) =n(n + 1)(4n − 1)3.Answer:Base Case: (n = 1)(LHS)1Xi=1(2i)(2i − 1) = (2)(2 − 1) = 2(RHS)1(1 + 1)(4 − 1)3=2(3)3= 22 = 2√Inductive Hypothesis: (n = k)kXi=1(2i)(2i − 1) =k(k + 1)(4k − 1)3Inductive Step: (n = k + 1)Show:k+1Xi=1(2i)(2i − 1) =(k + 1)((k + 1) + 1)(4(k + 1) − 1)31Proof:k+1Xi=1(2i)(2i − 1) =kXi=1(2i)(2i − 1) +k+1Xi=k+1(2i)(2i − 1)=kXi=1(2i)(2i − 1) + 2(k + 1)(2(k + 1) − 1)=k(k + 1)(4k − 1)3+ 2(k + 1)(2k + 1) (by the IH)=k(k + 1)(4k − 1)3+6(k + 1)(2k + 1)3=(k + 1) [k(4k − 1) + 6(2k + 1)]3=(k + 1)4k2+ 11k + 6 3=(k + 1)(k + 2)(4k + 3)3=(k + 1)((k + 1) + 1)(4(k + 1) − 1)3√3. Prove ∀n ∈ Z+nXi=1(4i − 3) = n(2n − 1).Answer:Base Case: (n = 1)(LHS)1Xi=1(4i − 3) = 4(1) − 3 = 1(RHS) n(2n − 1) = 1(2 − 1) = 11 = 1√Inductive Hypothesis: (n = k)kXi=1(4i − 3) = k(2k − 1)Inductive Step: (n = k + 1)Show:k+1Xi=1(4i − 3) = (k + 1)(2(k + 1) − 1)Proof:k+1Xi=1(4i − 3) =kXi=1(4i − 3) +k+1Xi=k+1(4i − 3)=kXi=1(4i − 3) + (4(k + 1) − 3)= k(2k − 1) + 4(k + 1) − 3 (by the IH)= 2k2− k + 4k + 4 − 3 = 2k2+ 3k + 1= (k + 1)(2k + 1) = (k + 1)(2(k + 1) − 1)√24. Prove ∀n ∈ Z+nYi=12i= 2n2+n22.Answer:Base Case: (n = 1)(LHS)1Yi=12i= 2(RHS) 2(12+12)= 21= 22 = 2√Inductive Hypothesis: (n = k)kYi=12i= 2k2+k22Inductive Step: (n = k + 1)Show:k+1Yi=12i= 2k+12+(k+1)22Proof:k+1Yi=12i= kYi=12i! k+1Yi=k+12i!= kYi=12i!2k+1=2k2+k222k+1(by the IH)= 2k2+k22+k+1= 2k+k2+2k+22= 2(k+1)+(k2+2k+1)2= 2k+12+(k+1)22√5. Recall the recursive definition of the Fibonacci sequence:F1= 1F2= 1Fk= Fk−1+ Fk−2for k > 2.Let’s perform a change of variable on the third line to get Fm+2= Fm+ Fm+1for m > 0, andFn+3= Fn+1+ Fn+2for n ≥ 0.Prove these interesting facts about this sequence:(a) ∀n ∈ Z+nXk=1Fk= Fn+2− 1Answer:Base Case: (n = 1)(LHS)1Xk=1Fk= F1= 1(RHS) F1+2− 1 = F3− 1 = 2 − 1 = 11 = 1√3Inductive Hypothesis: (n = p)pXk=1Fk= Fp+2− 1Inductive Step: (n = p + 1)Show:p+1Xk=1Fk= Fp+3− 1Proof:p+1Xk=1Fk=pXk=1Fk+p+1Xk=p+1Fk=pXk=1Fk+ Fp+1= Fp+2− 1 + Fp+1(by the IH)= Fp+1+ Fp+2− 1= Fp+3− 1 (by the definition of the Fib. seq.)(b) ∀n ∈ Z+nXk=1F2k= Fn· Fn+1.Answer:Base Case: (n = 1)(LHS)1Xk=1F2k= F21= 1(RHS) F1· F1+1= F1· F2= 1 · 1 = 11 = 1√Inductive Hypothesis: (n = p)pXk=1F2k= Fp· Fp+1Inductive Step: (n = p + 1)Show:p+1Xk=1F2k= Fp+1· Fp+2Proof:p+1Xk=1F2k=pXk=1F2k+p+1Xk=p+1F2k=pXk=1F2k+ F2p+1= Fp· Fp+1+ F2p+1(by the IH)= Fp+1(Fp+ Fp+1)= Fp+1· Fp+2√(by the definition of the Fib.
View Full Document
Unlocking...