Induction proof with Fibonacci numbers

Question

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?

Answer 1

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$.

Answer 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}$$

Answer 3

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.