2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the great answer! :) $\endgroup$ – JZ555 Nov 6 '13 at 17:24
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.