Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers

up vote 1 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|improve this answer
    
Thanks for the great answer! :) –  JZ555 Nov 6 '13 at 17:24
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.