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?
Best Answer
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$.