The Fibonacci sequence as $f(n)$
(1) show that $f(n) \le (\frac{7}{4})^n$, for all$ n \ge 0$
(2) show that $f(n) \ge \frac{1}{3}(\frac{3}{2})^n$, for all $ n \ge 1$
thanks.
Asked
Active
Viewed 198 times
0
-
Without using the closed form? – Ishan Banerjee Feb 05 '13 at 07:10
1 Answers
4
HINT Use induction and the recurrence for the Fibonacci numbers i.e. $$F_{n+1} = F_n + F_{n-1}$$ For part $(1)$, check base cases and by induction $F_{n-1} \leq \left(\dfrac{7}4 \right)^{n-1}$ and $F_{n} \leq \left(\dfrac{7}4 \right)^{n}$. Hence, all you need to prove is $$\left(\dfrac{7}4 \right)^{n-1} + \left(\dfrac{7}4 \right)^{n} \leq \left(\dfrac{7}4 \right)^{n+1}$$
Similarly, for part $(2)$, check base cases and by induction $F_{n-1} \geq \dfrac13 \left(\dfrac32 \right)^{n-1}$ and $F_{n} \geq \dfrac13 \left(\dfrac32 \right)^{n}$. Hence, all you need to prove is $$\dfrac13 \left(\dfrac32 \right)^{n-1} + \dfrac13 \left(\dfrac32 \right)^{n} \geq \dfrac13 \left(\dfrac32 \right)^{n+1}$$