# 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 :)!

-
– lab bhattacharjee Jun 15 '13 at 13:49
Are you trying to find out what $\alpha$ and $\beta$ are? I think your coefficients are wrong... – 6005 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
@ThomasAndrews: ah yes, didn't realize the title didn't parse right. a = $(1+\sqrt(5))/2$ and b = $(1-\sqrt(5))/2$ – Bas Jun 15 '13 at 13:59
Wait, that formula isn't true for $n=1$. There is something wrong with this formula. – Thomas Andrews Jun 15 '13 at 14:06

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