Proof by induction requires us to start by confirming that our goal is possible. In our case, we wish to show that F(n) ≤ 2n-1 is true for any natural number, n, where F(1) = F(2) = 1 and F(n) = F(n - 1) + F(n - 2).
Thus, we are required to show that this statement is true for the first natural number, the number 1. We call this the basis of induction:
Is F(1) = 1 ≤ 21-1 a true statement? That is the first thing you must decide.Now we introduce our hypothesis, we claim that F(k) ≤ 2k-1
is true for all natural numbers from 1 to k.Finally, we are required to show that F(k + 1) ≤ 2k
under the assumption that our hypothesis holds.Well, F(k + 1) = F(k) + F(k - 1) ≤ 2k-1 + 2k-2 by definition of F(n) and by our hypothesis.Therefore we are required to show that 2k-1 + 2k-2 ≤ 2k is a true statement.
If we can successfully do these things then, by the principle of induction, our goal is true.
As you mentioned, this function generates the famous Fibonacci sequence which has many intriguing properties.
Start by checking the first first values of n:
f(1) = 1 ≤ 21-1 = 20 = 1. TRUE.
So we know it is true for all n up to and including n = 3.
We've shown it is certainly true that f(k) ≤ 2k-1 for k = 3, because we tested that explicitly. If we can prove that given this, then f(k+1) ≤ 2k, then it must work for all positive values of k. In other words,
In inequalities, we can add the same quantity to both sides and still have a valid inequality. Therefore, let's add something to both sides.
f(k) + f(k-1) ≤ 2k-1 + f(k-1)
But since f(k-1) ≤ 2[k-1] - 1 (we showed that is true for k = 3 at the outset), then we have a third part to the inequality we can add to the end:
f(k) + f(k-1) ≤ 2k-1 + f(k-1) ≤ 2k-1 + 2[k-1] - 1
By definition though, the left side equals f(k+1), though, right? And let's just drop the middle section which has outlived its usefulness.
Thus we have f(k+1) ≤ 2k-1 + 2k-2.
Can you simplify the right side?
Stephen La Rocque
Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.