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.
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\).
