CMSC250 Spring 2004 Homework 7 Answers Due 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 or you will lose points n Y f i 1 Simplify this expression ln e i 1 Answer ln n Y h i ef i ln ef 1 ef 2 ef n i 1 ln ef 1 ln ef 2 ln ef n f 1 f 2 f n n X f i i 1 2 Prove n Z n X i 1 2i 2i 1 n n 1 4n 1 3 Answer Base Case n 1 1 X LHS 2i 2i 1 2 2 1 2 i 1 RHS 1 1 1 4 1 2 3 2 3 3 2 2 Inductive Hypothesis n k k X k k 1 4k 1 2i 2i 1 3 i 1 Inductive Step n k 1 k 1 X k 1 k 1 1 4 k 1 1 Show 2i 2i 1 3 i 1 1 Proof k 1 X 2i 2i 1 i 1 k X 2i 2i 1 i 1 k X k 1 X 2i 2i 1 i k 1 2i 2i 1 2 k 1 2 k 1 1 i 1 n X 3 Prove n Z k k 1 4k 1 2 k 1 2k 1 3 k k 1 4k 1 6 k 1 2k 1 3 3 k 1 k 4k 1 6 2k 1 2 3 k 1 4k 11k 6 3 k 1 k 2 4k 3 3 k 1 k 1 1 4 k 1 1 3 by the IH 4i 3 n 2n 1 i 1 Answer Base Case n 1 1 X LHS 4i 3 4 1 3 1 i 1 RHS n 2n 1 1 2 1 1 1 1 Inductive Hypothesis n k k X 4i 3 k 2k 1 i 1 Inductive Step n k 1 k 1 X Show 4i 3 k 1 2 k 1 1 i 1 Proof k 1 X 4i 3 i 1 k X i 1 k X k 1 X 4i 3 4i 3 i k 1 4i 3 4 k 1 3 i 1 k 2k 1 4 k 1 3 2 by the IH 2 2k k 4k 4 3 2k 3k 1 k 1 2k 1 k 1 2 k 1 1 2 4 Prove n Z n Y i 2 2 2 n n2 2 i 1 Answer Base Case n 1 1 Y LHS 2i 2 i 1 1 1 RHS 2 2 2 21 2 2 2 Inductive Hypothesis n k k 2 Y k k2 i 2 2 2 i 1 Inductive Step n k 1 k 1 k 1 2 k 1 Y 2 2 Show 2i 2 i 1 Proof k 1 Y k Y 2i i 1 2i i 1 2 k 22 k 1 Y 2 k k2 2 2i k Y 2i 2k 1 2 2 k 1 k2 2k 1 2 i 1 i k 1 k 1 k2 k 1 2 2 by the IH k k2 2k 2 2 2 k 1 k 1 2 2 2 5 Recall the recursive definition of the Fibonacci sequence F1 1 F2 1 Fk Fk 1 Fk 2 for k 2 Let s perform a change of variable on the third line to get Fm 2 Fm Fm 1 for m 0 and Fn 3 Fn 1 Fn 2 for n 0 Prove these interesting facts about this sequence a n Z n X Fk Fn 2 1 k 1 Answer Base Case n 1 1 X LHS F k F1 1 k 1 RHS F1 2 1 F3 1 2 1 1 1 1 3 Inductive Hypothesis n p p X Fk Fp 2 1 k 1 Inductive Step n p 1 p 1 X Show Fk Fp 3 1 k 1 Proof p 1 X Fk k 1 p X Fk k 1 p 1 X Fk k p 1 p X Fk Fp 1 k 1 Fp 2 1 Fp 1 by the IH Fp 1 Fp 2 1 Fp 3 1 b n Z n X by the definition of the Fib seq Fk2 Fn Fn 1 k 1 Answer Base Case n 1 1 X LHS Fk2 F12 1 k 1 RHS F1 F1 1 F1 F2 1 1 1 1 1 Inductive Hypothesis n p p X Fk2 Fp Fp 1 k 1 Inductive Step n p 1 p 1 X Show Fk2 Fp 1 Fp 2 k 1 Proof p 1 X k 1 Fk2 p X k 1 Fp Fk2 p 1 X Fk2 k p 1 2 Fp 1 Fp 1 p X 2 Fk2 Fp 1 k 1 by the IH Fp 1 Fp Fp 1 Fp 1 Fp 2 by the definition of the Fib seq 4
View Full Document
Unlocking...