Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Where did you "get" this proof? It is best to cite sources when using other peoples' material. –  Nicholas R. Peterson Sep 17 '13 at 3:12
    
I got it from link –  Sush Sep 17 '13 at 3:18
1  

2 Answers 2

up vote 4 down vote accepted

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$.

share|improve this answer
    
To show that $F_2=1$ you can simply notice that $(a^2-b^2)/(a-b)=a+b$ and use Vieta's formulas. (Of course, this assumes that the OP already knows Vieta's formulas.) –  Martin Sleziak Sep 17 '13 at 6:31
1  
@Martin: If not, it still makes the arithmetic easier; I’m incorporating that much into my answer. Thanks! –  Brian M. Scott Sep 17 '13 at 6:32

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$.

share|improve this answer
    
Thank you, Sir. But how is it enough to show that (a^(n+1))−(b^(n+1))=(a^n)−(b^n)+(a^(n−1))−(b^(n−1)). –  Sush Sep 17 '13 at 3:41
1  
You are welcome. If you agree with the previous displayed line, the line you quoted in your comment is obtained by multiplying through by $a-b$. –  André Nicolas Sep 17 '13 at 3:44
    
Thank you. Now the last question:how is it enough to show that (a^(n+1))=(a^n)+(a^(n−1)) and (b^(n+1))=(b^n)+(b^(n−1))? –  Sush Sep 17 '13 at 3:50
1  
Those two together imply that $a^{n+1}-b^{n+1}=a^n-b^n+a^{n-1}-b^{n-1}$, for we can rewrite this equation as $a^{n+1}-a^n-a^{n-1}=b^{n+1}-b_n-b^{n-1}$. If we prove that $a^{n+1}=a^n+a^{n-1}$, then we know $a^{n+1}-a^n -a_{n-1}=0$, same with the $b$'s. –  André Nicolas Sep 17 '13 at 3:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.