Inductive proof of the closed formula for the Fibonacci sequence [duplicate]

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.


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.