Induction Proofs with the Fibonacci Sequence (A-Level & Further Maths Extension)

Introduction

The Fibonacci sequence is defined using the recurrence formula:

fn+2 = fn+1 + fn for n ≧ 1 with f1 = 1 and f2 = 1.

The sequence begins 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

In this post, we explore four elegant results that can be proven using mathematical induction (including strong induction).

1. Every Fourth Fibonacci Number Is Divisible by 3

Theorem

The subsequence f4n is divisible by 3 for n ≧ 1.

Proof (ordinary induction)

When n = 1, f4 = 3 which is divisible by 3.

Assume that the statement is true for n = k, so f4k is divisible by 3. Now,

3f4k+1 is divisible by 3 and so too is 2f4k using the inductive hypothesis. Hence f4(k+1) is divisible by 3 which means that the statement is true when n = k+1. So f4n is divisible by 3 for n ≧ 1 by mathematical induction.

2. Inequality

Proof (strong induction)

Now assume that the statement is true for n = i for all 1 ≤ i ≤ k for some k∈ℕ and k ≥ 2. In standard mathematical induction you have a single induction hypothesis; if you have multiple inductive hypotheses you can use “strong induction” to prove the result for n=k+1. So from our inductive hypotheses we can say that:

When n=k+1, we have

So the statement is true for n=k+1 and hence true for n ≥ 1 by strong induction.

3. Binet’s Formula for the Fibonacci Numbers

Binet's formula for the nth term of the Fibonacci sequence is:

Proof (strong induction)

First note that φ²＝φ+1, since

So two base cases are satisfied. Now assume that the statement is true for n = i for all 1 ≤ i ≤ k for some k∈ℕ and k ≥ 2. When n=k+1, we have

So the statement is true for n=k+1 and hence true for n ≥ 1 by strong induction.

4. Fibonacci Numbers as Sums of Binomial Coefficients

Each term of the Fibonacci sequence can be expressed as a sum of binomial coefficients:

Here the nCr terms are summed as long as n ≥ r.

Proof (strong induction)

This will require Pascal's combinatorial identity,

To see this,

Now, when n=1 and n=2, we have:

So two base cases are satisfied. Now assume that the statement is true for n = i for all 1 ≤ i ≤ k for some k∈ℕ and k ≥ 2. When n=k+1, we have

So the statement is true for n=k+1 and hence true for n ≥ 1 by strong induction.

Conclusion

These results illustrate how both ordinary and strong induction can be applied to the Fibonacci sequence. They also give insight into divisibility patterns, exponential bounds, closed forms, and combinatorial structures hidden inside the sequence.