# Fibonacci sequence: how to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$?

Let $F_n$ be the $n$th Fibonacci number. Let $\alpha = \frac{1+\sqrt5}2$ and $\beta =\frac{1-\sqrt5}2$.

How to prove that $\alpha^n=\alpha\cdot F_n + F_{n-1}$?

I'm completely stuck on this question. I've managed to take the equation form of $F$ and come down to:

$$\frac1{\sqrt 5}(\alpha^n(\alpha+\alpha^{-1}) - \beta^n(\alpha+\beta^{-1}))$$

But I'm lost from there on. I'm not looking for the answer, but any pointers would be great :)!

-
Welcome to Math.SE. Thank you for your question. To help us answer it, please share the context, as well as what you've tried so far. If this is homework, please tag it as such. Also, it will be much easier for everyone if you use MathJax to format your question. –  vadim123 Jun 15 '13 at 13:48
–  lab bhattacharjee Jun 15 '13 at 13:49
@vadim123: done thanks to myuseristhis:). Thanks for the headsup –  Bas Jun 15 '13 at 13:55
Are you trying to find out what $\alpha$ and $\beta$ are? I think your coefficients are wrong... –  Goos Jun 15 '13 at 13:55
Do you mean $F_{n+1}$? Alway, what are $\alpha,\beta$? –  Thomas Andrews Jun 15 '13 at 13:58

It's easier to prove this by induction. Note that $F_1\alpha + F_0=\alpha+0=\alpha^1$.

Then use that $\alpha$ is a root of $x^2-x-1=0$ to show that if $\alpha^n=F_n\alpha+F_{n-1}$ then it follows that $\alpha^{n+1}=F_{n+1}\alpha + F_{n}$.

-
Could you explain what $\alpha$ is a root of $x^2 -x -1=0$ means? –  Bas Jun 15 '13 at 14:18
@Bas: That means that $\alpha$ is a number that satisfies the equation. So we have $\alpha^2-\alpha-1=0$. –  Fredrik Meyer Jun 15 '13 at 14:25

First, for $n=1$, \begin{align} \alpha^1 &=\alpha F_1+F_0\\ &=\alpha\cdot1+0\\ &=\alpha \end{align} Suppose it's true for $n$, then because $\alpha^2=\alpha+1$, \begin{align} \alpha^{n+1} &=\alpha\cdot\alpha^n\\ &=\alpha(\alpha F_n+F_{n-1})\\ &=\alpha^2F_n+\alpha F_{n-1}\\ &=(\alpha+1)F_n+\alpha F_{n-1}\\ &=\alpha(F_n+F_{n-1})+F_n\\ &=\alpha F_{n+1}+F_n \end{align} Thus, it is true for $n+1$. By induction, the identity is true for all $n\ge1$.

-
the realization that $\alpha^2=\alpha+1$ did it. This was even introduced in one of the assignments before this one, should have known this :'). Thanks a lot! –  Bas Jun 15 '13 at 14:34

Using Euler-Binet Formula,

$$F_{n+1}=\frac{\alpha^{n+1}-\beta^{n+1}}{\alpha-\beta}$$

$$=\frac{\alpha^n(\alpha-\beta)+\beta\cdot \alpha^n-\beta^{n+1}}{\alpha-\beta}$$

$$=\alpha^n+\beta\cdot \frac{\alpha^n-\beta^n}{\alpha-\beta}$$

$$=\alpha^n+\beta\cdot F_n =\alpha^n-\frac{F_n}\alpha\text{ as }\alpha\cdot \beta=-1$$

$$\implies \alpha\cdot F_{n+1}+F_n=\alpha^{n+1}$$

-
@ThomasAndrews, was just going to complete this –  lab bhattacharjee Jun 15 '13 at 14:16