Inductive proof of the closed formula for the Fibonacci sequence Fibonacci numbers $f(n)$ are defined recursively:  $f(n) = f(n-1) +f(n-2)$ for $n > 2$ and $f(1) = 1$, $f(2) = 1$.
They also admit a simple closed form:
$$\sqrt 5 f( n ) = \left(\dfrac{1+ \sqrt 5}{2}\right)^n- \left(\dfrac{1 - \sqrt 5}{2}\right)^n \tag1$$

How to prove (1) using induction?

Remarks
One could get (1) by the general method of solving recurrences: look for solutions of the form $f(n)=r^n$, then fit them to the initial values.
But there should be a more concrete proof for this specific sequence, using the principle of mathematical induction.
 A: I'll be dealing with the inductive step only.
Let $\alpha =\dfrac{1+\sqrt 5}{2}$ and $\beta =\dfrac{1-\sqrt 5}{2}$.
Note that $\alpha^2=1+\alpha$ and $\beta ^2=1+\beta$. This is a direct consequence of the fact that $\alpha$ and $\beta$ are roots of $x^2-x-1$.
Suppose that given $n\in \Bbb N$ such that $n\ge 3$, it holds that $$\tag {I.H.}(\forall k\in \Bbb N)(k<n\implies\sqrt 5f(k)=\alpha^k-\beta ^k)$$
Since $n\ge 3$, $f(n)=f(n-2)+f(n-1)$, therefore $\sqrt 5f(n)=\sqrt 5f(n-2)+\sqrt 5f(n-1)$ and applying the $\text{I.H.}$ it follows that $$\sqrt 5f(n)=\alpha ^{n-2}-\beta ^{n-2}+\alpha ^{n-1}-\beta ^{n-1}=\left(\alpha^{n-2}+\alpha^{n-1}\right)-\left(\beta ^{n-2}+\beta ^{n-1}\right).$$
Now factoring out appropriately yields $$\sqrt 5f(n)=\alpha ^{n-2}(1+\alpha )-\beta ^{n-2}(1+\beta).$$
Now use $\alpha^2=1+\alpha$ and $\beta ^2=1+\beta$ to conclude.
A: So we check:

*

*Base cases: Show $$\sqrt{5}\ f(1)= \frac{1+\sqrt{5}}{2}-\frac{1-\sqrt{5}}{2}$$ and $$\sqrt{5}\ f(2)= \frac{(1+\sqrt{5})^2}{2}-\frac{(1-\sqrt{5})^2}{2}.$$  You'll need to check two base cases since the recurrence has depth $2$.


*Inductive step:  Assume $$\sqrt{5}\ f(k)= \frac{(1+\sqrt{5})^k}{2^k}-\frac{(1-\sqrt{5})^k}{2^k}$$ for all $1 \leq k \leq N$.  Use this to deduce that $$\sqrt{5}\ f(N+1)= \frac{(1+\sqrt{5})^{N+1}}{2^{N+1}}-\frac{(1-\sqrt{5})^{N+1}}{2^{N+1}}.$$
The way to do this is to pull out terms that look like the above formula for $\sqrt{5}\ f(N)$.  It should be possible to manipulate the formula to obtain $\sqrt{5}\ f(N)+\sqrt{5}\ f(N-1)$, then use the inductive hypothesis.


*Conclude, by induction, that the formula holds for all $n \geq 1$.
Note, this is known as Binet's Formula for the Fibonacci Numbers.
