# Some proof question about Fibonacci sequence

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.

-
Without using the closed form? –  Ishan Banerjee Feb 5 '13 at 7:10
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}$$