Question

Let a₁=a₂=1, a₃= 2 and a_n=a_n-1+a_n-2 for n>= 3. If the given sequence is a Fibonacci sequence, then prove using induction that :-
a₁+a₂+......+a_n= a_n+2 -1

Answer 1

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, ...(add the last two numbers to get the next). They are defined recursively by the formula f1=1, f2=1, fn= fn-1 + fn-2 for n>=3.
We will derive a formula for the sum of the first n fibonacci numbers and prove it by induction.

n =	1	2	3	4	5	6	7	8	9	10
fn =	1	1	2	3	5	8	13	21	34	55
sum fn =	1	2	4	7	12	20	33	54

Notice from the table it appears that the sum of the first n terms is the (nth+2) term minus 1.



Proof by induction
Let P(n) be the statement "f1+f2+f3+...fn=f(n+2) - 1
1.) Since f1=f(1=2) - 1 = f3 - 1 = 2 - 1 = 1
P(1) is true.
2.) Suppose that p(k) is true for a positive integer k.
Then f1+f2+...+fk = f(k+2) - 1
Therefore, f1+f2+...fk+f(k+1) = f(k+2) - 1 + f(k+1)
= f(k+1 + f(k+2) - 1 = f(k+3) - 1
because f(k+1) + f(k+2) = f(k+3) by definition of Fibonacci numbers
f(k+3) = f(k+3) - 1 + f(k+3) -2. QED.