mathschallenge.net logo

Fibonacci Sequence

Problem

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

Fn = 
1
radical5
1 + radical5
2
n minus 
1 minus radical5
2
n

Solution

We shall prove this by induction, starting by showing that F1 = F2 = 1.

F1 = 
1
radical5
1+radical5
2
1 minus 
1minusradical5
2
1
  = 
1
2radical5
1+radical5 minus 1minusradical5
  = 
1
2radical5
2radical5
  = 1
F2 = 
1
radical5
1+radical5
2
2 minus 
1minusradical5
2
2
 = 
1
radical5
6+2radical5
4
 minus 
6minus2radical5
4
 = 
1
radical5
3+radical5
2
 minus 
3minusradical5
2
  = 
1
radical5
radical5
  = 1

Now we shall consider Fn + Fn+1.

 
1
radical5
1+radical5
2
nminus
1minusradical5
2
n + 
1

radical5
1+radical5
2
n+1minus
1minusradical5
2
n+1
 = 
1
radical5
1+radical5
2
n+
1+radical5
2
n+1minus
1minusradical5
2
nminus
1minusradical5
2
n+1
 = 
1
radical5
1+radical5
2
n1+
1+radical5
2
minus
1minusradical5
2
n1+
1minusradical5
2
 = 
1
radical5
1+radical5
2
n
3+radical5
2
 minus 
1minusradical5
2
n
3minusradical5
2
But in calculating F2 we have seen that,
1+radical5
2
2 = 
3+radical5
2
Similarly,
1minusradical5
2
2 = 
3minusradical5
2
therefore Fn + Fn+1 = 
1
radical5
1+radical5
2
n
1+radical5
2
2minus
1minusradical5
2
n
1minusradical5
2
2
 = 
1
radical5
1+radical5
2
n+2minus
1minusradical5
2
n+2
 = Fn+2

Which is consistent with the result expected; that is, Fn+2 = Fn + Fn+1. As it works for F1 and F2 it must work for all n.

Problem ID: 135 (Nov 2003)     Difficulty: 4 Star

Only Show Problem