Relationship between Fibonacci's secuence and $x^2 - x - 1$. On the end of Apostol's Mathematical Analysis' first chapter, one can find the following exercise (and I paraphrase):

Prove that the $n$-th term of the Fibonacci sequence is given by $$x_n = \frac{a^n - b^n}{a-b}$$ Where $a$ and $b$ are the roots of $x^2 - x - 1$.

Apostol also states that $x_{n+1} = x_n + x_{n-1}$. I've tried a proof by induction on $n$ in this formula. I assumed it hold, and I went on with the second step: I assume it holds for $k\leq n$ and tried to show it must hold for $n+1$:
\begin{array}{rcl}
x_{n+1} & = & x_n + x_{n-1} \\[0.2cm]
 & = & \displaystyle \frac{a^n - b^n}{a-b} + \frac{a^{n-1} - b^{n-1}}{a-b} \\
 & = & \displaystyle \frac{(a^n + a^{n-1})-(b^n + b^{n-1})}{a-b}
\end{array}
So, if I prove that $a^n + a^{n-1} = a^{n+1}$ (and the same with $b$), I should be done. So, as a lemma, I try to demonstrate this by induction, but it doesn't seem to hold.
My questions, then, are: Is there another way of proving this statement?, Is my lemma true?
 A: When you simplified, you messed up. The first numerator in the third line should be 
$$
a^n + a^{n-1}
$$
and the second should be 
$$
-(b^n + b^{n-1})
$$
From there, you'll find it easy. (Factor out $a^n$ from the result equation.)
A: $$x^2-x-1=0$$
$$x^2=x+1$$
Multiply that by $x$ and you get:
$$x^3=x^2+x$$
Then replace $x^2$ by $x+1$, which yields:
$$x^3=2x+1$$
Repeat this process. Using induction, you can easily prove that:
$$x^n=x_nx+ x_{n-1} $$
Since $a$ and $b$ are the solutions of $x^2-x-1=0$ then they are also the solutions of $x^n=x_nx+1$,which means that:
 $$a^n=x_na+x_{n-1}$$
$$b^n=x_nb+ x_{n-1} $$
Subtracting these two equations yields:
$$a^n-b^n=x_n(a-b)$$
$$x_n=\frac{a^n-b^n}{a-b}$$
A: My favorite way to prove the Fibonacci statement is the following:
Let $f(x)$ be the generating function for the Fibonacci sequence.  In other words, $$f(x)=\sum_{i=0}^\infty f_nx^n$$ where $f_n$ is the $n$-th Fibonacci number (I'll assume that $f_0=0$ and $f_1=1$, you can choose a different starting place.
The recurrence in Fibonacci numbers gives that $$f=xf+x^2f+x.$$  This happens because multiplication by $x$ and $x^2$ shift the elements of the power series up by 1 and 2, respectively.  The reason for the $x$ is that the lowest order terms don't add correctly (you would need a Laurent series to avoid this term).
Taking the equation above, we could solve for $f$ to get $$f(1-x-x^2)=x$$ or that $$f=\frac{x}{1-x-x^2}.$$  
The next step is to use partial fractions, to rewrite $\frac{x}{1-x-x^2}$ as a sum of two fractions whose denominators are $x-a$ and $x-b$ (where $a$ and $b$ are the two roots of $1-x-x^2$.
Finally, use the power series expansion of $\frac{1}{1-x}$ (scaled appropriately) to write out the terms of $f$.
A: Here's a large hint:
Consider the following limit:
$$\lim_{n \to \infty} \frac{F_{n+1}}{F_n}$$
Suppose that this limit exists, let's call it '$L$'.
Then
$$L = \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \lim_{n \to \infty} 1 + \frac{F_{n-1}}{F_n}$$
It can be shown that $$\lim_{n \to \infty} \frac{F_{n-1}}{F_n} = \lim_{n \to \infty} \frac{F_{n}}{F_{n+1}} = \frac{1}{L}$$
So $$L = \lim_{n \to \infty} \frac{F_{n+1}}{F_n} = 1 + \frac{1}{L}$$.
Solving for L, you will find it must satisfy:
$$L^2 - L - 1 = 0$$
