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?

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