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.