mathschallenge.net

Problem

Given the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, ... defined by the second order recurrence relation, F_n+2 = F_n + F_n+1. Prove that the nth term, F_n, is given by:

Fn =

1 5

1 + 5 2

n

1 5 2

n

Solution

We shall prove this by induction, starting by showing that F₁ = F₂ = 1.

F1	=	1 5 1+5 2 1    15 2 1
	=	1 25 1+5    15
	=	1 25 25
	=	1

F2	=	1 5 1+5 2 2    15 2 2
	=	1 5 6+25 4    625 4
	=	1 5 3+5 2    35 2
	=	1 5 5
	=	1

Now we shall consider F_n + F_n+1.

	1 5 1+5 2 n 15 2 n  +  1 5 1+5 2 n+1 15 2 n+1
=	1 5 1+5 2 n + 1+5 2 n+1 15 2 n 15 2 n+1
=	1 5 1+5 2 n 1+ 1+5 2 15 2 n 1+ 15 2
=	1 5 1+5 2 n 3+5 2    15 2 n 35 2

But in calculating F2 we have seen that,

1+5 2

2

=

3+5 2

Similarly,

15 2

2

=

35 2

Fn + Fn+1	=	1 5 1+5 2 n 1+5 2 2 15 2 n 15 2 2
	=	1 5 1+5 2 n+2 15 2 n+2
	=	Fn+2

Which is consistent with the result expected; that is, F_n+2 = F_n + F_n+1. As it works for F₁ and F₂ it must work for all n.