$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$
How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} \right )^{n-1}$$ for all$$ n\geq l_{a}$$, I have to find the smallest value for $$l_{a}$$
On
$f_1 = 0 \leq \left(\frac{1+\sqrt{5}}{2}\right)^0 = 1$
$f_2 = 1 \leq \frac{1+ \sqrt{5}}{2} \approx 1.618$
Suppose $f_k \leq \left(\frac{1+\sqrt{5}}{2}\right)^{k-1}, f_{k+1} \leq \left( \frac{1 + \sqrt{5}}{2} \right)^{k}$
Then $f_{k+2} = f_k + f_{k+1} \leq \left(\frac{1+\sqrt{5}}{2}\right)^{k-1} + \left( \frac{1 + \sqrt{5}}{2} \right)^{k} = \left(\frac{1 + \sqrt{5}}{2}\right)^{k+1}$
Proof of last statement: $a^{k+1} = a^k + a^{k-1} \rightarrow a^2 - a - 1 \rightarrow a = \frac{1 + \sqrt{5}}{2}$
$(1)$ $f_1 \leq (\frac{1+\sqrt{5}}{2})^{1-1} \Rightarrow 0 \leq 1,f_2 = 1 \leq \frac{1+ \sqrt{5}}{2} \approx 1.618 $. $\textbf{True}$
$(2)$ Next: Suppose for some $\textbf{k}$ $\geq n$ we have $f_k \leq (\frac{1+\sqrt{5}}{2})^{k-1}$
$(3)$ We want to show: $f_{k+1} \leq (\frac{1+\sqrt{5}}{2})^{k}$
$(4)$ Well, $f_{k+1} = f_{k-1}+f_{k-2}$
$(5)$ By hypothesis we have bounds on both of the things on right of the inequality.
$(6)$ Thus: $f_{k+1} \leq \ 2(\frac{1+\sqrt{5}}{2})^{k-1} \leq (\frac{1+\sqrt{5}}{2})^{k-1} (\frac{1+\sqrt{5}}{2})^{k} = (\frac{1+\sqrt{5}}{2})^{k}$