I'm a bit unsure about going about a Fibonacci sequence proof using induction. the question asks:
The Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, …, which is commonly
described by $ F_1 = 1, F_2 = 1 \text { and } F_{n+1} = F_n + F_{n−1}, ∀ \space n ∈ \mathbb{N}, n ≥ 2.$Prove by induction that the $n^{th}$ term in the sequence is
$$ F_n = \frac
{(1 + \sqrt 5)^n − (1 −\sqrt 5)^n}
{2^n\sqrt5} $$
I believe that the best way to do this would be to Show
true for the first step, assume true for all steps $ n ≤ k$ and then prove true for $n = k + 1.$
However I'm unsure how to go about this, I'd really appreciate any help or if anyone has a better way of proving this through induction.
Best Answer
First of all, we rewrite
$$F_n=\frac{\phi^n−(1−\phi)^n}{\sqrt5}$$
Now we see \begin{align} F_n&=F_{n-1}+F_{n-2}\\ &=\frac{\phi^{n-1}−(1−\phi)^{n-1}}{\sqrt5}+\frac{\phi^{n-2}−(1−\phi)^{n-2}}{\sqrt5}\\ &=\frac{\phi^{n-1}−(1−\phi)^{n-1}+\phi^{n-2}−(1−\phi)^{n-2}}{\sqrt5}\\ &=\frac{\phi^{n-2}(\phi+1)−(1−\phi)^{n-2}((1-\phi)+1)}{\sqrt5}\\ &=\frac{\phi^{n-2}(\phi^2)−(1−\phi)^{n-2}((1-\phi)^2)}{\sqrt5}\\ &=\frac{\phi^n−(1−\phi)^n}{\sqrt5}\\ \end{align}
Where we use $\phi^2=\phi+1$ and $(1-\phi)^2=2-\phi$. Now check the two base cases and we're done!
Turns out we don't need all the values below $n$ to prove it for $n$, but just $n-1$ and $n-2$ (this does mean that we need base case $n=0$ and $n=1$).