Let $(F_n)_{n = 1} ^ \infty$ be the Fibonnaci sequence. Show that $F_n \geq\phi^{n-2}\hspace{0.35cm} \forall n \in \mathbb{N},\hspace{0.35cm} n \geq 2$ where $\phi$ is the golden ratio.
This is my solution,
Proof method: strong induction on $n$. Let $P(n)$ denote $F_n \geq\phi^{n-2}$.
$\underline{Base \hspace{0.1cm}case:}$ Show that $P(n)$ holds for $n = 2$. We have that $F_2 \geq \phi^{0} = 1$. Hence, the base case holds.
$\underline{Inductive \hspace{0.1cm}hypothesis:}$ Assume that $P(n)$ holds where $2 \leq n \leq k$ and $k\geq 2.$ In particular assume that $F_k \geq\phi^{k-2}$ and $F_{k-1} \geq\phi^{k-3}$.
$\underline{Inductive \hspace{0.1cm}step:}$ Prove $P(n)$ holds for $ n = k +1$. By the recursive definition we have that,
$$F_{k+1} = F_{k} + F_{k-1}$$
Using the inductive hypothesis we can then write,
$$F_{k+1} \geq \phi^{k-2} + \phi^{k-3}$$
$$F_{k+1} \geq \phi^{k-3} (1 + \phi)$$
But $\phi + 1 = \phi ^ 2$ and hence,
$$F_{k+1} \geq \phi^{k-3} ( \phi^2)$$ $$F_{k+1} \geq \phi^{k-1} $$
as required.
The solution I'm presented with considers $n = 3$ in the base case as well. I'm having a hard time understanding why the base case $n = 3$ is needed, I cannot see why it makes a difference. I thought we could just assume that $n = 3$ holds in the inductive hypothesis?
$*$ My only thought as to why we may need to consider $n = 3$ too is because we effectively assert $F_{4} \geq \phi^{1} + \phi^{0}$ in the inductive step. In order to do this we must know $n = 3$ holds unequivocally. I'm imagining this as being an extra base case in way, namely the base case where we confirm that the 'recursive inequality' holds - not sure if that's the correct terminology.
Could someone offer an explanation as to why we must consider $n = 3$ too? My guess $(*)$ just doesn't sit will with me.
