Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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

share|cite|improve this answer
Thanks for the great answer! :) – JZ555 Nov 6 '13 at 17:24

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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