# Fibonacci sequence Proof by strong induction

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.

• Well you basically "just" need to show that $F_{n+2} - F_{n+1} - F_n = 0$ assuming that the formula for $F_{n+1}$ and $F_n$ is true. – Zubzub Mar 31 '17 at 13:30
• math.stackexchange.com/questions/350165/… – Bram28 Mar 31 '17 at 16:27

$$F_n=\frac{\phi^n−(1−\phi)^n}{\sqrt5}$$
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$).