The Fibonacci numbers F_n are defined by: F_1 = F_2 = 1, F_{n+2} = F_{n+1} + F_n \textrm{ for } n\ge 1.

 

The numbers are 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, …

 

The Fibonacci numbers have many interesting properties, and the proofs of these properties provide excellent examples of Proof by Mathematical Induction. Here are two examples. The first is quite easy, while the second is more challenging.

 

Theorem

 

Every fifth Fibonacci number is divisible by 5.

 

Proof

 

We note first that F_5 = 5 is certainly divisible by 5, as are F_{10} = 55 and F_{15} = 610. How can we be sure that the pattern continues?

 

We shall show that: IF the statement “F_n is divisible by 5″ is true for some natural number m, THEN the statement is also true for the natural number m+5.

 

Now

 

F_{m+5} = F_{m+4} + F_{m+3}

= (F_{m+3} + F_{m+2}) + F_{m+3}

= 2F_{m+3} + F_{m+2}

= 2(F_{m+2} + F_{m+1}) + (F_{m+1} + F_m)

= 2F_{m+2} + 3F_{m+1} + F_m

= 2(F_{m+1} + F_m) +3F_{m+1} + F_m

= 5F_{m+1} + 3F_m.

 

Since we know that F_m is divisible by 5, it is now clear that F_{m+5} is also divisible by 5. But F_5 is divisible by 5, therefore so is F_{10}, and also F_{15}, and so on.

 

By the Principle of Mathematical Induction, every fifth Fibonacci number is divisible by 5.

 

Theorem

 

F_{n+1}^2 - F_nF_{n+2} = (-1)^n \textrm{ for all } n

 

Proof

 

We note first that the statement is true when n=1, since F_{1+1}^2 - F_1F_{1+2} = F_2^2 - F_1F_3 = 1^2 - 1\times 2 = 1-2 = -1 = (-1)^1.

 

We now show that: IF the statement true for some natural number m, THEN it is also true for the next number, namely m+1.

 

So let us assume that F_{m+1}^2 - F_mF_{m+2} = (-1)^m. (*)

 

Then

F_{m+2}^2 - F_{m+1}F_{m+3}

= F_{m+2}^2 - F_{m+1}(F_{m+2} + F_{m+1})

= F_{m+2}^2 - F_{m+1}F_{m+2} - F_{m+1}^2

= F_{m+2}(F_{m+2} - F_{m+1}) - F_{m+1}^2

= F_{m+2}F_m - F_{m+1}^2

= -(F_{m+1}^2 - F_{m+2}F_m)

= -(-1)^m, using (*)

= (-1)^{m+1}

 

and we have shown that the result is true for the next number, m+1. But we noted at the beginning that the result is true for m=1. It is therefore true for the next number, 2, and therefore true for the next number, 3, and for 4, 5, 6, … and so on.

By the Principle of Mathematical Induction, the result is true for all natural numbers.

—————————————-

Originally written by John Webb.

How clear is this post?