Assignment #13

Here’s a solution to Assignment #12 problem 18 from section 2.4 on page 139

to prove:

F(1) + F(3) + ... + F(2n-1) = F(2n) where the F’s represent Fibonnacci numbers

F(1) = 1 by definition

2n+3

2n+2

2n+1

2n

2n-1

2n-2

2n-3

Definitions of Fibonacci numbers to remember

F(2n) = F(2n-1) + F(2n-2)

F(2n-1) = F(2n-2) + F(2n-3)

F(2n+1) = F(2n) + F(2n-1)

F(2n+2) = F(2n+1) + F(2n)

F(1) + F(3) + ... + F(2k-1) = F(2k) ASSUMED

F(1) + F(3) + ... + F (2k-1) + F(2(k+1)-1) = F(2(k+1)) TO PROVE

F(1) + F(3) + ... + F( 2k–1) + F(2k+2-1) = F(2k+2)

F(1) + F(3) + ... + F( 2k-1) + F(2k+1)

F(2k) + F(2k+1)

note that above line matches green line in box so

F(2k+2) = F(2k+2) PROVED

Written assignment

Section 2.4 page 139

6

14

19

39

41