The Fibonacci numbers are a famous integer sequence: (Fn)n=0 := 0,1,1,2,3,5,8,13

Question

The Fibonacci numbers are a famous integer sequence: (Fn)n=0 := 0,1,1,2,3,5,8,13,21,34,55,89,...

defined recursively by F0 =0,F1 =1, and Fn = Fn1+Fn2 for n 2.

1. Find the partial sums F0 +F1 +F2, F0 +F1 +F2 +F3, F0 +F1 +F2 +F3 +F4, F0 +F1 +F2 +F3 +F4 +F5,

F0 +F1 +F2 +F3 +F4 +F5 +F6, and F0 +F1 +F2 +F3 +F4 +F5 +F6 +F7.

2. Compare your partial sums above with the terms of the Fibonacci sequence. Do you see any patterns? Make a conjecture for F0 +F1 +···+F8 and F0 +···+F9. Decide if your conjecture is true by actually computing the sums. Revise your conjecture if necessary.

3. Make a conjecture for F0 + F1 + · · · + Fn and verify it is correct using mathematical induction.

Explanation / Answer

1)

F0+F1+F2=0+1+1=2

F0+F1+F2+F3=0+1+1+2=4

F0+F1+F2+F3+F4=0+1+1+2+3=7

F0+F1+F2+F3+F4+F5=0+1+1+2+3+5=12

F0+F1+F2+F3+F4+F5+F6=0+1+1+2+3+5+8=20

F0+F1+F2+F3+F4+F5+F6+F7=0+1+1+2+3+5+8+13=33

2)

The pattern we got is that each sum Sn=F0+F1+F2+..........+Fn=Fn+2-1

F0+F1+F2+F3+F4+F5+F6+F7+F8=0+1+1+2+3+5+8+13+21=54 which is F10-1

F0+F1+F2+F3+F4+F5+F6+F7+F8+F9=0+1+1+2+3+5+8+13+34=88 which is F11-1

hence conjecture for our partial sum of terms is true.....

3)

Sn=F0+F1+F2+..........+Fn=Fn+2-1

The proof is by induction. The formula holds for n = n, and suppose it holds for some n 1, adding Fn+1 to both sides gives

F0+F1+F2+..........+Fn+Fn+1=Fn+2-1+Fn+1

F0+F1+F2+..........+Fn+Fn+1=Fn+3-1

so the identity holds for n + 1 as well. By induction, the result holds for all

hence verified..........................

AlLL THE BeSt dear.........................

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.