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.