Hello James,

Proof by induction requires us to start by confirming that our goal is possible.  In our case, we wish to show that F(n) ≤ 2^n-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 ≤ 2^1-1 a true statement?  That is the first thing you must decide.

is true for all natural numbers from 1 to k.

under the assumption that our hypothesis holds.

As you mentioned, this function generates the famous Fibonacci sequence which has many intriguing properties.
Tyler

Hi James.

Start by checking the first first values of n:

f(1) = 1 ≤ 2^1-1 = 2⁰ = 1. TRUE.
f(2) = 1 ≤ 2^2-1 = 2¹ = 2. TRUE.
f(3) = f(1) + f(2) = 1 + 1 = 2 ≤ 2^3-1 = 2² = 4. 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) ≤ 2^k-1 for k = 3, because we tested that explicitly. If we can prove that given this, then f(k+1) ≤ 2^k, then it must work for all positive values of k. In other words,
if it works for 3, it must work for 4 and that implies 5 and so on to infinity.

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.
Let's add [ f(k-1) ]:

f(k) + f(k-1) ≤ 2^k-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) ≤ 2^k-1 + f(k-1) ≤ 2^k-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) ≤ 2^k-1 + 2^k-2.

Can you simplify the right side?

Stephen La Rocque