# Induction proof with Fibonacci numbers

Prove by induction that for Fibonacci numbers from some index $i > 10$

$1.5^i ≤ f_i ≤ 2^i$

Notice! Because Fibonacci number is a sum of 2 previous Fibonacci numbers, in the induction hypothesis we must assume that the expression holds for k+1 (and in that case also for k) and on the basis of this prove that it also holds for k+2.

This where I've got so far:

Base case: $i = 11$
$f_{11} = 89$
$1.5^{11} ≤ 89 ≤ 2^{11}$ OK!

Induction hypothesis:
$1.5^{k+1} ≤ f_{k+1} ≤ 2^{k+1}$

Induction step:
$1.5^{k+2} ≤ f_{k+2} ≤ 2^{k+2}$

Now I have no idea how to continue from here. Could someone help?

If $\alpha^k\le f_k\le \beta^k$ and $\alpha^{k+1}\le f_{k+1}\le \beta^k$, then $$f_{k+2}=f_k+f_{k+1}\ge \alpha^k+\alpha^{k+1}=\alpha^{k+2}\cdot(\frac1{\alpha^2}+\frac1\alpha)$$ and $$f_{k+2}=f_k+f_{k+1}\le \beta^k+\beta^{k+1}=\beta^{k+2}\cdot(\frac1{\beta^2}+\frac1\beta),$$ so in order to conclude $$\alpha^{k+2}\le f_{k+2}\le \beta^{k+2}$$ is is sufficent to have $\frac1{\alpha^2}+\frac1\alpha\ge 1$ and $\frac1{\beta^2}+\frac1\beta\le 1$. You can verify that this is indeed true for $\alpha=\frac32$ and $\beta=2$.

When dealing with induction results about Fibonacci numbers, we will typically need two base cases and two induction hypotheses, as your problem hinted.

You forgot to check your second base case: $1.5^{12}\le 144\le 2^{12}$

Now, for your induction step, you must assume that $1.5^k\le f_k\le 2^k$ and that $1.5^{k+1}\le f_{k+1}\le 2^{k+1}.$ We can immediately see, then, that $$f_{k+2}=f_k+f_{k+1}\le 2^k+f_{k+1}\le 2^k+2^{k+1}= 2^k(1+2)\le 2^k\cdot 4=2^{k+2}$$ As for the other inequality, we similarly see that $$f_{k+2}=f_k+f_{k+1}\ge 1.5^k+1.5^{k+1}=1.5^k(1+1.5)=1.5^k\cdot 2.5\ge1.5^k\cdot 2.25=1.5^{k+2}$$

• Thanks for the great answer! :) Commented Nov 6, 2013 at 17:24

This problem/proof is asking an interesting question: to show that, at some point, the growth in Fibonacci numbers is bounded by two exponential functions: $$1.5^i$$ from below and $$2^i$$ from above. Right away, we know that the ratio of sequential Fibonacci numbers approaches the Golden Ratio = 1.618..., so we know that the upper bound and lower bound functions will indeed bracket the growth of the Fibonacci numbers.

Another way of looking at the answer that @Hagen von Eitzen provided is as follows. Both $$\frac{1}{\alpha^2} + \frac{1}{\alpha} = 1$$ and $$\frac{1}{\beta^2} + \frac{1}{\beta} = 1$$ lead to the same polynomial expression of the form: $$x^2 - x - 1 = 0$$. One of the solutions to this expression is $$x = 1.61803...$$ which is the Golden Ratio. The polynomial and its roots are shown in the Figure below.

For the expression with $$\alpha$$, you need $$\frac{1}{\alpha^2} + \frac{1}{\alpha} \geq 1$$, which leads to $$0 \geq \alpha^2 - \alpha - 1$$. The (positive) solutions for $$\alpha$$ will be less than 1.618..., and $$\alpha = 1.5$$ will work.

For the expression with $$\beta$$, you need $$\frac{1}{\beta^2} + \frac{1}{\beta} \leq 1$$, which leads to $$0 \leq \beta^2 - \beta - 1$$. The solutions for $$\beta$$ will be greater than 1.618..., and $$\beta = 2$$ will work.

• @JoséCarlosSantos - I respectfully disagree. I was adding to Hagen 's very nice answer and I was merely trying to state that Golden Ratio is actually the boundary for $\alpha$ and $\beta$. Exponential functions where the base is less than the Golden ratio would be the lower bound and functions where the base is greater than the Golden ratio would be the upper bound. I sorry you think this adds no value -- perhaps for you, it doesn't, but it may for others. Furthermore, if it adds no value, then no one in the community will upvote it. Let it be. I enjoyed answering it! Commented Sep 9, 2019 at 6:00