Please help to understand Fibonacci numbers' property.

Question

Theorem: The Fibonacci numbers are defined recursively thus: $$x_{n+1} = x_n + x_{n-1}$$ with $$x_1=x_2=1.$$

Prove that $$x_n=(a^n-b^n)/(a-b),$$ where $a$ and $b$ are the roots of the quadratic equation $x^2-x-1=0$.

I found this proof, apparently by Apostol:

Observe that $$x_{n+1} = x_n + x_{n-1},$$ and thus we consider $$x^{n+1} = x^n +x^{n-1},$$ i.e., consider $$x^2 = x+1$$ with two roots, $a$ and $b$. If we let $$F_n = (a^n -b^n)/(a-b),$$ then it is clear that $F_1=1$, $F_2=1$, and $F_{n+1}=F_n+F_{n+1}$ for $n>1$. So $F_n = x_n$ for all $n$.

I can't understand this proof.

Please help.

Answer 1

The words It is clear that are a bit of an exaggeration: you have to do a bit of work to fill in the details. Take the assertions one at a time.

1. $F_1=1$: Since $F_1=\frac{a^1-b^1}{a-b}$, this is indeed clear.

2. $F_2=1$: To verify this, you’ll probably want to figure out what $a$ and $b$ actually are. Applying the quadratic formula to $x^2-x-1=0$, we see that they are given by $\frac{1\pm\sqrt5}2$, and therefore $$F_2=\frac{a^2-b^2}{a-b}=a+b=\frac{(1+\sqrt5)+(1-\sqrt5)}2=1\;.$$

3. $F_{n+1}=F_n+F_{n-1}$ for $n>1$: this is just a slightly messy calculation: $$\begin{align*}F_n+F_{n-1}&=\frac{a^n-b^n}{a-b}+\frac{a^{n-1}-b^{n-1}}{a-b}\\&=\frac{(a^n+a^{n-1})-(b^n+b^{n-1})}{a-b}\\&=\frac{a^{n-1}(a+1)-b^{n-1}(b+1)}{a-b}\\&\overset{*}=\frac{a^{n-1}(a^2)-b^{n-1}(b^2)}{a-b}\\&=\frac{a^{n+1}-b^{n+1}}{a-b}\\&=F_{n+1}\;,\end{align*}$$ where the starred step follows from the fact that $a$ and $b$ satisfy the equation $x^2=x+1$.

From (1) and (2) we know that $x_1=F_1$ and $x_2=F_2$. If there is any $n$ such that $x_n\ne F_n$, let $m$ be the smallest such $n$. Clearly $m\ne 1$ and $m\ne 2$, so $m\ge 3$. Now

• from (3) we know that $F_m=F_{m-1}+F_{m-2}$;
• $F_{m-1}=x_{n-1}$ and $F_{m-2}=x_{m-2}$, because $m$ was the smallest index at which the $F$’s and $x$’s differed; and
• $x_{m-1}+x_{m-2}=x_m$ by the definition of the Fibonacci numbers.

Putting the pieces together, we see that

$$F_m=F_{m-1}+F_{m-2}=x_{m-1}+x_{m-2}=x_m\;,$$

contradicting the choice of $m$. Thus, there is no $n\ge 1$ such that $x_n\ne F_n$, and we conclude that the numbers $F_n$ are in fact the Fibonacci numbers $x_n$.

Answer 2

There are two possible questions you may have: (i) Why did the writer decide to do things this way? (ii) Why is the formula right? We only address the second question.

We have $a^0=1$ and $b^0=1$, so $\frac{a^0-b^0}{a-b}=0=F_0$.

Also, $\frac{a^1-b^1}{a-b}=1=F_1$.

It remains to show that if $G_n=\frac{a^n-b^n}{a-b}$, then $G$ satisfies the Fibonacci recurrence $G_{n+1}=G_n+G_{n-1}$. Thus we want to show that $$\frac{a^{n+1}-b^{n+1}}{a-b}=\frac{a^{n}-b^{n}}{a-b}+\frac{a^{n-1}-b^{n-1}}{a-b},$$ or equivalently that $$a^{n+1}-b^{n+1}=a^n-b^n+a^{n-1}-b^{n-1}.$$ It is enough to show that $a^{n+1}=a^n+a^{n-1}$, and $b^{n+1}=b^n+b^{n-1}$. We do the first. The argument for the second is the same.

We know that $a$ satisfies the equation $a^2=a+1$. Multiplying both sides by $a^{n-1}$ gives $a^{n+1}=a^n+a^{n-1}$, which is what we wanted to show.

We have shown that $F(0)=G(0)$ and $F(1)=G(1)$. We have also shown that the sequence $(F_n)$ and $(G_n)$ satisfy the same recurrence. It follows that $F_n=G_n$ for all $n$.