Fibonacci sequence Proof by strong induction

Question

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.

Answer 1

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$).