Having studied proof by induction and met the Fibonacci sequence, it’s time to do a few proofs of facts about the sequence. We’ll see three quite different kinds of facts, and five different proofs, most of them by induction. We’ll also see repeatedly that the statement of the problem may need correction or clarification, so we’ll be practicing ways to choose what to prove as well!
An equality: sum of squares of terms
A typical Fibonacci fact is the subject of this 2001 question:
Fibonacci Proof This Fibonacci proof is giving me major problems: F(2n) = (F(n))^2 + (F(n-1))^2 , I'm a biochem major, and not a math major, so I'm lost... help!?
Let’s check it out first. Recall that as usually written, \(F_1=1\), \(F_2=1\), \(F_3=2\), \(F_4=3\), \(F_5=5\) and so on. If I take \(n=2\), we get \(F_{2n}=F_4=3\), while \(F_n^2+F_{n-1}^2=F_2^2+F_1^2=1^2+1^2=2\). Something is wrong; we can’t prove something that isn’t true!
But I do see that \(1^2+2^2=5\); maybe he is numbering the sequence so that \(F_0=1\), \(F_1=1\), \(F_2=2\), \(F_3=3\), \(F_4=5\). Then, again taking \(n=2\), we get \(F_{2n}=F_4=5\), while \(F_n^2+F_{n-1}^2=F_2^2+F_1^2=2^2+1^2=5\). This turns out to be valid.
Doctor Rob answered, starting with the same check:
This is false, provided you are numbering the Fibonacci numbers so that F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, and so on. Proving something that is false will not prove to be an easy task. To see the falsity, notice that when n = 2, the right-hand side of your equation becomes F(2)^2 + F(1)^2 = 1^2 + 1^2 = 2 = F(3), whereas your equation would say that this equals F(4).
In keeping with this remark, he wisely changed the indexes in the equation rather than the indexing of the sequence itself:
That means that your proof must be of the following equation, instead: F(2*n-1) = F(n)^2 + F(n-1)^2. This one is true, and one proof goes like this.
Let’s check the restated claim: Using the standard sequence and taking \(n=2\), we get \(F_{2n-1}=F_3=2\), while \(F_n^2+F_{n-1}^2=F_2^2+F_1^2=1^2+1^2=2\).
First proof (by Binet’s formula)
Let the roots of x^2 - x - 1 = 0 be a and b. The explicit expressions for a and b are a = (1+sqrt[5])/2, b = (1-sqrt[5])/2. In particular, a + b = 1, a - b = sqrt(5), and a*b = -1. Also a^2 = a + 1, b^2 = b + 1. Then the Binet Formula for the k-th Fibonacci number is F(k) = (a^k-b^k)/(a-b).
We’ve seen this before; his a is \(\phi\), and his b is \(1-\phi=-\frac{1}{\phi}=-\Phi\). I find that I like the form with a and b better, because it makes the formula symmetrical and memorable. Now we’ll be transforming the right-hand side (RHS) of the claimed identity into the left-hand side (LHS) as our proof.
Substitute this in the right-hand side of the identity you are trying to prove: F(n)^2 + F(n-1)^2 = (a^n-b^n)^2/(a-b)^2 + (a^(n-1)-b^(n-1))^2/(a-b)^2. Now put the right-hand side of this over the common denominator (a-b)^2, expand the numerator, and simplify using a*b = -1. That should give you F(n)^2 + F(n-1)^2 = (a^[2*n]+b^[2*n]+a^[2*n-2]+b^[2*n-2])/(a-b)^2.
Let’s see if it does: $$F_n^2+F_{n-1}^2= \frac{(a^n-b^n)^2}{(a-b)^2}+\frac{(a^{n-1}-b^{n-1})^2}{(a-b)^2}\\= \frac{(a^n-b^n)^2+(a^{n-1}-b^{n-1})^2}{(a-b)^2}\\= \frac{a^{2n}-2a^nb^n+b^{2n}+a^{2n-2}-2a^{n-1}b^{n-1}+b^{2n-2}}{(a-b)^2}\\= \frac{a^{2n}-2(-1)^n+b^{2n}+a^{2n-2}-2(-1)^{n-1}+b^{2n-2}}{(a-b)^2}\\= \frac{a^{2n}+b^{2n}+a^{2n-2}+b^{2n-2}}{(a-b)^2}$$
At this point, we need to keep in mind our goal, to make this look like $$F_{2n-1}=\frac{a^{2n-1}-b^{2n-1}}{(a-b)}.$$ That will suggest ways to use the known relationships between a and b to adjust various exponents.
Now multiply each of the last terms in the numerator by -a*b = 1, factor out (a-b) from the numerator, and cancel it with a factor from the denominator, and recognize the Binet formula for F(2*n-1).
Here we go: $$\frac{a^{2n}+b^{2n}+a^{2n-2}+b^{2n-2}}{(a-b)^2}=\frac{a^{2n}+b^{2n}+(-ab)a^{2n-2}+(-ab)b^{2n-2}}{(a-b)^2}\\= \frac{aa^{2n-1}+bb^{2n-1}-ba^{2n-1}-ab^{2n-1}}{(a-b)^2}\\= \frac{(a-b)a^{2n-1}-(a-b)b^{2n-1}}{(a-b)^2}\\=\frac{a^{2n-1}-b^{2n-1}}{(a-b)}=F_{2n-1}$$
So we’ve completed a non-inductive proof. But we can also do it using induction and a little less algebra.
Second proof (by induction)
We start with the base case:
Another proof would go like this: It is true for n = 1 and n = 2, by direct verification.
Carrying that out, the bases cases are: $$n=1: F_1^2+F_{1-1}^2=F_1^2+F_0^2=1^2+0^2=1; F_{2\cdot 1-1}=F_1=1\\ n=2: F_2^2+F_{2-1}^2=F_2^2+F_1^2=1^2+1^2=2; F_{2\cdot 2-1}=F_3=2$$
Note that by the usual definition, we can’t do this for \(n=0\), so the statement should have specified positive integers; but in fact, we could define \(F_{-1}=F_1-F_0=1-0=1\), and then we would have $$n=0: F_0^2+F_{0-1}^2=F_0^2+F_{-1}^2=0^2+1^2=1; F_{2\cdot 0-1}=F_{-1}=1$$
In the proof, we will be applying both the “forward” recursion $$F_n=F_{n-1}+F_{n-2},$$ and the “backward” recursion $$F_{n-2}=F_n-F_{n-1},$$ and the “middle” recursion $$F_{n-1}=F_n-F_{n-2}.$$
Note that, as we saw when we first looked at the Fibonacci sequence, we are going to use “two-step induction”, a form of strong induction, which requires two base cases.
Now we make the (strong) inductive hypothesis, which we will apply when \(n>2\):
Suppose it is true for all n <= k. Then F(2*k-3) = F(k-1)^2 + F(k-2)^2, F(2*k-1) = F(k)^2 + F(k-1)^2.
Here we have applied the hypothesis to two particular values of \(n\le k\), namely \(n=k-1\) and \(n=k\).
Our goal will be to show that \(F_{2n-1} = F_n^2 + F_{n-1}^2\) is true also when \(n=k+1\), which means $$F_{2(k+1)-1} = F_{k+1}^2 + F_{(k+1)-1}^2\\F_{2k+1} = F_{k+1}^2 + F_{k}^2.$$ Be watching for this!
Then
F(2*k+1) = F(2*k) + F(2*k-1), by the Fibonacci recursion,
= 2*F(2*k-1) + F(2*k-2), by the Fibonacci recursion,
= 3*F(2*k-1) - F(2*k-3), by the Fibonacci recursion,
= 3*[F(k)^2 + F(k-1)^2] - [F(k-1)^2 + F(k-2)^2],
by the hypotheses above,
= 3*F(k)^2 + 2*F(k-1)^2 - F(k-2)^2,
= 3*F(k)^2 + 2*F(k-1)^2 - [F(k) - F(k-1)]^2,
by the Fibonacci recursion,
= 2*F(k)^2 + 2*F(k)*F(k-1) + F(k-1)^2,
= 2*F(k)^2 + 2*F(k)*[F(k+1)-F(k)] + [F(k+1)-F(k)]^2,
by the Fibonacci recursion,
= F(k+1)^2 + F(k)^2.
Formatted nicely and filling in details: $$F_{2k+1} = F_{2k}+F_{2k-1}\\ = (F_{2k-1}+F_{2k-2})+F_{2k-1} = 2F_{2k-1}+F_{2k-2}\\ =2F_{2k-1}+(F_{2k-1}-F_{2k-3})=3F_{2k-1}-F_{2k-3}\\ =3(F_k^2 + F_{k-1}^2)-(F_{k-1}^2 + F_{k-2}^2)\\ =3F_k^2 + 3F_{k-1}^2-F_{k-1}^2 – F_{k-2}^2=3F_k^2 + 2F_{k-1}^2- F_{k-2}^2\\ =3F_k^2 + 2F_{k-1}^2- (F_k-F_{k-1})^2\\ =3F_k^2 + 2F_{k-1}^2- F_k^2+2F_kF_{k-1}-F_{k-1}^2=2F_k^2+2F_kF_{k-1}+F_{k-1}^2\\ =2F_k^2+2F_k(F_{k+1}-F_k)+(F_{k+1}-F_k)^2\\ =2F_k^2+2F_kF_{k+1}-2F_k^2+F_{k+1}^2-2F_{k+1}F_k+F_k^2=F_{k+1}^2+F_k^2.$$ And there we are!
This leaves open the question of how he found this path to the goal. The basic idea is that he had to come up with \(F_{2k-1}\) and \(F_{2k-3}\) in order to apply the hypotheses, so he used recursion for that; then he had to get everything in terms of just \(F_{k+1}^2\) and \(F_k^2\) in order to reach the goal, for which more recursion was needed. Everything is directed by the goal.
Applying the Principle of Mathematical Induction (strong form), we can conclude that the statement is true for every n >= 1.
This is a fairly typical, though challenging, example of inductive proof with the Fibonacci sequence.
An inequality: sum of every other term
This question from 1998 involves an inequality, which can require very different thinking:
A Fibonacci Proof by Induction I need to prove the following by induction: Let u_1, u_2, ..... be the Fibonacci sequence. Prove by induction that for n > 0: u_(n-1) + u_(n-3) + u_(n-5) + ... < u_n I am really stuck on this one because I don't even know where to begin. I am not sure how to prove that this is true for S_1 and then prove it is true for S_k and S_k+1. Your help in the matter would be most appreciated. Thank you, Michael
Michael is using \(S_k\) to mean the statement applied to \(n=k\).
Again, let’s check the claim as a way to make sure we understand it. For \(n=5\), and using our usual \(F_n\) rather than \(u_n\), it is saying (\(S_5\)) that $$F_4+F_2<F_5\\3+1<5,$$ which is true. For \(n=6\), it is saying (\(S_6\)) that $$F_5+F_3+F_1<F_6\\5+2+1<8,$$ which is false! It looks like once again we have to modify the claim. It may be that the “less than” should have been “less than or equal to”; or it could be that the sequence is being started at a different place. I myself would probably make the former guess, which we’ll see would be valid; but we’ll be doing it the latter way.
First proof: separating evens and odds
Two of us responded. Doctor Rob answered first, apparently making my observation and picking a start that will work, without explaining his thinking in detail:
You didn't tell me the values of u_1 and u_2, so I am not sure which Fibonacci sequence you mean. There are at least two different ones that are called by that name. This is important for establishing S_1. I will assume that u_1 = 1, u_2 = 2.
Using the usual sequence, \(S_1\) would be the statement that $$F_0<F_1\\0<1,$$ but probably Michael’s sequence doesn’t start at 0. That may be part of his difficulty! If so, we’d really start at \(S_2\): $$F_1<F_2\\1<1.$$ Again, this is false by our usual definition. This would be why Doctor Rob chose to start as he did: We can’t have the first two terms be equal!
Now, of course, we need to distinguish our sequence from the usual Fibonacci, so let’s revert to u. Here are the first few terms: $$u_1=1, u_2=2, u_3=3, u_4=5, u_5=8,\cdots$$
One simple approach is to separate this into two cases, n even and n odd. First consider the case where n is odd, n = 2k+1. Then let S_k be the statement that: u_(2k) + u_(2k-2) + u_(2k-4) + ... < u_(2k+1). Then S_1 is the statement that u_2 < u_3. That is true because u_2 = 2 and u_3 = 3.
This parallels what we have done previously for Fibonacci, using what Doctor Rob called “double-step induction”, with two base cases and strong induction. In this case, we will be able to do two parts separately and use weak induction.
When n is odd, the summation is over even terms with index less than n.
Don’t miss the fact that he has redefined \(S_k\), using his k rather than n; so this \(S_1\) is what we previously would have called \(S_3\).
Assume S_k is true for some value of k. Then add u_(2k) to both sides. On the right side, use the Fibonacci recursion to conclude that u_(2k-1) + u_(2k) = u_(2k+1) = u(2[k+1]-1). Then you have proven S_(k+1) by assuming S_k, so S_k implies S_(k+1). By the Principle of Mathematical Induction, S_k is true for all k, so the statement you are trying to prove is true for all odd values of n.
I think there is a small error here, and he may have had \(u_{2k-1}\) rather than \(u_{2k+1}\) for his RHS. I’ll change the instructions a little to fit what we have.
We are assuming that $$u_{2k} + u_{2k-2} + u_{2k-4} + … < u_{2k+1},$$ and we want to show that $$u_{2(k+1)} + u_{2(k+1)-2} + u_{2(k+1)-4} + … < u_{2(k+1)+1}\\u_{2k+2} + u_{2k} + u_{2k-2} + … < u_{2k+3}.$$
In order to obtain the new RHS, we need to add \(u_{2k+2}\), which happens to be exactly what we need to add on the LHS:
$$u_{2k+2}+u_{2k} + u_{2k-2} + u_{2k-4} + … < u_{2k+2}+u_{2k+1}\\ u_{2k+2}+u_{2k} + u_{2k-2} + u_{2k-4} + … < u_{2k+3}.$$ That’s exactly what we needed to show.
Next consider the case where n is even, n = 2k. Now let T_k be the statement that: u_(2k-1) + u_(2k-3) + u_(2k-5) + ... < u_(2k). Then T_1 is the statement that u_1 < u_2. That is true because u_1 = 1 and u_2 = 2.
We’re doing all the same things with a different expression for n. He used a different name for the kth statement, because it is a different statement than before.
Assume T_k is true for some value of k. Then add u_(2k+1) to both sides. On the right side, use the Fibonacci recursion to conclude that u_(2k) + u_(2k+1) = u_(2k+2) = u(2[k+1]). Then you have proven T_(k+1) by assuming T_k, so T_k implies T_(k+1). By the Principle of Mathematical Induction, T_k is true for all k, so the statement you are trying to prove is true for all even values of n.
This time, we are assuming that $$u_{2k-1} + u_{2k-3} + u_{2k-5} + … < u_{2k},$$ and we want to show that $$u_{2k+1} + u_{2k-1} + u_{2k-3} + … < u_{2k+2}.$$
In order to obtain the new RHS, we need to add \(u_{2k+1}\), which is also what we need to add on the LHS:
$$u_{2k+1}+u_{2k-1} + u_{2k-3} + u_{2k-5} + … < u_{2k}+u_{2k+1}\\= u_{2k+1}+u_{2k-1} + u_{2k-3} + u_{2k-5} + … < u_{2k+2}.$$ As before, that’s exactly what we needed to show.
So by working separately with odd and even indices, we were able to use weak induction to prove the claim for all n:
Second proof
Four hours later, Doctor Anthony answered, more concisely as usual, and evidently making Doctor Rob’s assumption about the starting point:
For the first step: u(3)+u(1) < u(4) (yes, because u(4) = u(3)+u(2) and u(2) > u(1)) u(4)+u(2) < u(5) (yes, because u(5) = u(4)+u(3) and u(3) > u(2))
These, which we can call \(P_4\) and \(P_5\), are the first two cases if we require at least two terms and don’t define \(u_0\); he assumes the one-term cases \(P_2\) and \(P_3\), and there is no \(P_1\). Thus, he will be showing that the claim is true as long as we choose \(u_1<u_2<u_3\), which is not true for the traditional Fibonacci sequence, 1, 1, 2, … . On the other hand, if we change every < to ≤, we can see that everything will still work, and the base case will now be true.
Now, he doesn’t explicitly separate into odd and even cases as Doctor Rob did, but does the same work:
Assume it is true for n = k: u(k-1) + u(k-3) + ... < u(k) Now add u(k+1) to both sides and we have: u(k+1) + u(k-1) + u(k-3) + ... < u(k) + u(k+1) u(k+1) + u(k-1) + u(k-3) + ... < u(k+2)
This is the same expression as we had before, except that k is replaced by k+2. So if the result is true for n = k it is also true for n = k+2. But it is true for n = 4, so it is true for n = 6, and if it is true for n = 6, then it is true for n = 8, 10, .... It is also true for n = 5 and so for n = 7, 9, 11, ... So the result is true for all positive integral values of n.
What we have is two interleaved chains of inference:
(I started this within what he called the base case.)
Inside-out: any number is a sum of terms
Another 2001 question turned everything around:
Sum of Distinct Fibonacci Numbers How do you show that every positive integer is a sum of distinct terms of the Fibonacci sequence?
Rather than proving something about the sequence itself, we’ll be proving something about all positive integers.
For example, the number 10 can be expressed as \(5+3+2\) or as \(8+2\); and 100 is \(87+13\).
Doctor Floor answered:
Hi Sam, thanks for writing. We can even prove a slightly better theorem: that each number can be written as the sum of a number of nonconsecutive Fibonacci numbers. We prove it by (strong) mathematical induction.
This change will eliminate my example of \(5+3+2 = 10\), where 2 and 3 are consecutive terms; it has the effect of making the sums unique, though we won’t be proving that here.
1. The statement is clearly true for n = 1, 2, and 3 since 1 = F_1, 2 = F_3, and 3 = F_4, which we may consider as single term sums.
So we have three base cases; the statement is true for all \(n\le 3\) for a start.
2.
Suppose that the statement is true for all n <= m (this is the induction hypothesis for strong induction, while n = m is used for standard induction). We will prove that the statement is true for n = m+1.
If m+1 = F_t for some t, then it is trivially correct. In other cases we find the t such that F_t < m+1 < F_{t+1}.
Taking as an example \(n=m+1=12\), we suppose that the theorem is true for all numbers m less than 12. We first look for the greatest Fibonacci number less than or equal to 12. Since 12 itself is not a Fibonacci number (if it were, we would be done), we find that \(8<12<13\), so our \(F_t=F_6=8\).
Let q = m+1-F_t; then we can write q as a sum of nonconsecutive Fibonacci numbers according to the induction hypothesis. We also note that this sum does not contain F_{t-1} because:
q = m+1-F_t < F_{t+1} - F_t = F_{t-1}
In our example, \(q=12-8=4\), and we know that this can be written as a sum of nonconsecutive Fibonacci numbers, in this case \(4=3+1=F_4+F_2\). Therefore, we have shown that \(12=F_6+(F_4+F_2)=8+3+1\). How do we know none are consecutive? The sum for \(q=4\) can’t include \(F_5\) because 12 was less than \(F_7=13\), so \(q=12-F_6<F_7-F_6=F_5\).
So if we add F_t to the sum of nonconsecutive Fibonacci numbers for q, we have such a sum for m+1 as well. And the statement is true for n = m+1.
It is unusual that this inductive proof actually provides an algorithm for finding the Fibonacci sum for any number. Taking as an example 123, we can just look at a list of Fibonacci numbers going past 123, $$1, 1, 2, 3, 5, 8, 13, 21, 33, 54, 87, 141,$$ and work our way down: $$123-87=36\\36-33=3$$ so $$123=87+33+3=F_{11}+F_9+F_4$$
For more on this, see Ron Knott’s page: Using the Fibonacci numbers to represent whole numbers
That includes information about the “Fibonacci base system”, in which 123 = 10100001000, and a whole lot more. A somewhat related idea is “base phi”, humorously called “phinary numbers”, by which any number can be represented as a sum of powers of \(\phi\), just as binary numbers represent sums of powers of 2. You can read about both systems in Wikipedia:
Next week, we’ll look at some more non-inductive proofs.