Inductive proof of the closed formula for the Fibonacci sequence

Question

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.

Answer 1

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.

Answer 2

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.