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 :)!
 A: 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}$.
A: 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} $$
A: 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$.
A: More generally, if a sequence $x_n$ satisfies the Fibonacci recurrence $x_{n+2}=x_{n+1}+x_n$ for all $n\ge0$, then $x_n = x_1 F_n + x_0 F_{n-1}$ for all $n\ge1$. This follows immediately by induction.
Now apply this $x_n=\alpha^n$. The defining equation for $\alpha$ is $\alpha^2=\alpha+1$, and so $\alpha^{n+2}=\alpha^{n+1}+\alpha^n$ for all $n\ge0$. The result above then gives
$$
\alpha^{n} = x_n = x_1 F_n + x_0 F_{n-1} = \alpha^1 F_n + \alpha^0 F_{n-1} = \alpha F_n + F_{n-1}
$$
