Review question

# Can we prove these Fibonacci number results? Add to your resource collection Remove from your resource collection Add notes to this resource View your notes for this resource

Ref: R9868

## Solution

The Fibonacci numbers $F_n$ are defined by the conditions $F_0 = 0$, $F_1 = 1$ and $F_{n+1} = F_n + F_{n-1}$ for all $n \geq 1$. Show that $F_2 = 1$, $F_3 = 2$, $F_4 = 3$ and compute $F_5$, $F_6$ and $F_7$.

This tells us that to get the sequence $F_n$ we start with $0$ and $1$, and then find the next term by adding the previous two.

$0,1,1,2,3,5,8,13,21,....$

Using the given definition, we have $F_2 = F_1 + F_0 = 1 + 0 = 1, F_3 = F_2 + F_1 = 1 + 1 = 2, F_4 = F_3 + F_2 = 2 + 1 = 3,$ as required. Similarly, we have $F_5 = F_4 + F_3 = 3 + 2 = 5, F_6 = F_5 + F_4 = 5 + 3 = 8, F_7 = F_6 + F_5 = 8 + 5 = 13.$

Compute $F_{n+1}F_{n-1} - F_n^2$ for a few values of $n$; guess a general formula and prove it by induction, or otherwise.

When $n = 1$, we have $F_{n+1}F_{n-1} - F_n^2 = F_2 F_0 - F_1^2 = 1 \times 0 - 1^2 = -1$.

When $n = 2$, we have $F_{n+1}F_{n-1} - F_n^2 = F_3 F_1 - F_2^2 = 2 \times 1 - 1^2 = 1$.

When $n = 3$, we have $F_{n+1}F_{n-1} - F_n^2 = F_4 F_2 - F_3^2 = 3 \times 1 - 2^2 = -1$.

When $n = 4$, we have $F_{n+1}F_{n-1} - F_n^2 = F_5 F_3 - F_4^2 = 5 \times 2 - 3^2 = 1$.

We are now well placed to make a conjecture about the value of $F_{n+1}F_{n-1} - F_n^2$ for general $n$.

Claim $S_n$: $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$.

Proof of $S_n$: By induction on $n$.

Induction works like this; say we have a statement about positive integers, $S_n$.

We show $S_n$ is true for some positive integer $a$.

Then we assume $S_n$ is true for some general integer $m$, and derive from this that $S_{m+1}$ must be also true.

So $S_a$ is true, so $S_{a+1}$ is true, and so $S_{a+2}$ is true… and we’ve proved $S_n$ true for all $n \geq a.$

We prove ‘the $a$th domino falls’, and ‘if the $m$th domino falls, then the ($m+1$)th one does’. This means all the dominoes fall beyond and including domino $a$.

We’ve already checked the result for $n$ up to $4$. $\checkmark$ True for $1 \leq n \leq 4$.

Induction step: Suppose that the result holds for $n=m$, so $F_{m+1}F_{m-1} - F_m^2 = (-1)^m$.

Our target equation is $F_{m+2}F_{m} - F_{m+1}^2 = (-1)^{m+1}$. We’ll start with the left-hand side of this.

We’d like to use the result we’re supposing, so let’s get rid of $F_{m+2}$, using the definition of Fibonacci numbers that we’ve been given.

Then \begin{align*} F_{m+2}F_m - F_{m+1}^2 &= (F_{m+1} + F_m) F_m - F_{m+1}^2 \\ &= F_{m+1}F_k + F_m^2 - F_{m+1}^2 \\ &= F_{m+1}(F_m - F_{m+1}) + F_m^2.\qquad\text{(by factorising)} \end{align*}

Now we can use the definition of Fibonacci numbers again. We know that $F_{m+1} = F_m + F_{m-1}$, so rearranging we find that $F_m - F_{m+1} = -F_{m-1}$.

We can substitute that in the expression above, to get \begin{align*} F_{m+2}F_k - F_{m+1}^2 &= -F_{m+1}F_{m-1} + F_m^2 \\ &= -(F_{m+1}F_{m-1} - F_m^2) \\ &= - (-1)^m\quad \textrm{(using our assumption)} \\ &= (-1)^{m+1}. \checkmark \end{align*}

So by induction we are done. For $n \geq 1$, we have $F_{n+1}F_{n-1} - F_n^2 = (-1)^n$.

By induction on $k$, or otherwise, show that $F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$ for all positive integers $n$ and $k$.

Claim $S_k$: For each $k \geq 1$, we have $F_{n+k} = F_k F_{n+1} + F_{k-1}F_n$ for all $n \geq 1$.

Proof of $S_k$: By induction on $k$.

For $k = 1$, we have $F_{n+1} = 1 \times F_{n+1} + 0 \times F_n = F_1 \times F_{n+1} + F_0 \times F_n$. $\checkmark$ True for all $n \geq 1$.

Induction step: Suppose that the result is true for $1 \leq k \leq m$, so $F_{n+k} = F_{k} F_{n+1} + F_{k- 1}F_n$ for $1 \leq k \leq m, n \geq 1$.

Note that we are not just assuming $S_k$ for $k = m$, but for all the integers $1$ to $m$.

Instead of saying, ‘Let’s assume the $m$th domino falls’, we say, ‘Let’s assume the first $m$ dominoes all fall’.

This is known as Strong Induction.

We want to show that $F_{n+(m + 1)} = F_{m + 1}F_{n+1} + F_{m} F_n$ for all $n \ge 1$. Now

$F_{m + 1}F_{n+1} + F_{m} F_n = (F_m+F_{m-1})F_{n+1} + (F_{m-1}+F_{m-2})F_n$

$= (F_mF_{n+1}+F_{m-1}F_{n+1})+(F_{m-1}F_n+F_{m-2}F_n)$

$= (F_mF_{n+1}+F_{m-1}F_n)+(F_{m-2}F_n+F_{m-1}F_{n+1})$

$= F_{n+k}+ F_{n+k-1}$ (from our assumption)

$= F_{n+k+1}.$

And so we have that $S_k$ (for $1 \leq k \leq m, n \geq 1$) implies $S_k$ is true (for $1 \leq k \leq m + 1, n \geq 1$).

Thus our statement $S_k$ is true for all $k \geq 1$, all $n \geq 1$.