The Fibonacci numbers are defined by: ,

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 is certainly divisible by 5, as are and How can we be sure that the pattern continues?

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

Now

.

Since we know that is divisible by 5, it is now clear that is also divisible by 5. But is divisible by 5, therefore so is , and also , and so on.

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

**Theorem**

**Proof**

We note first that the statement is true when , since

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

So let us assume that (*)

Then

, using (*)

and we have shown that the result is true for the next number, . But we noted at the beginning that the result is true for . 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.

themba malusiOctober 18, 2015 at 8:40 amI think there is a mistake in the first of the Fibonacci pattern in I the inductive case in line 6 ,that was suppose to be 2(F_m+1 + F_m)+ 3F_m+1 + F_m

Jonathan ShockOctober 18, 2015 at 8:45 amCheers Themba, yes!

Some slightly more advanced topics on Mathemafrica – MathemafricaJanuary 17, 2018 at 10:06 am[…] Fibonacci and induction […]