Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ for all $n \in \mathbb Z^+$. [duplicate]

Question

Let $\alpha = \frac{1+\sqrt{5}}{2} \hskip 20pt \beta = \frac{1-\sqrt{5}}{2}$ be the two real roots of the quadratic equation $x^2 - x - 1 = 0.$ Prove that $f_n = \frac{\alpha^n - \beta^n}{\alpha - \beta}$ for all $n \in \mathbb Z^+$.

I'm confused as to how this could be simplified after doing the induction step where you add 1 to all of the "n's" making it, $f_n = \frac{\alpha^{n+1} - \beta^{n+1}}{\alpha - \beta}$

Answer 1

By the definition of Fibonacci numbers, \begin{align*} f_1\equiv&\,1,\\ f_2\equiv&\,1,\\ f_n\equiv&\,f_{n-1}+f_{n-2}\quad\forall n\in\mathbb Z_+:n\geq 3. \end{align*} You can check directly that $$f_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}\tag{$\clubsuit$}$$ does hold for $n\in\{1,2\}$.

Now let $n\geq 3$ and assume that ($\clubsuit$) is true up to $n-1$. Then, \begin{align*} f_n=&\,f_{n-1}+f_{n-2}=\frac{\alpha^{n-1}-\beta^{n-1}}{\alpha-\beta}+\frac{\alpha^{n-2}-\beta^{n-2}}{\alpha-\beta}=\frac{\left(\alpha^{n-2}+\alpha^{n-1}\right)-\left(\beta^{n-2}+\beta^{n-1}\right)}{\alpha-\beta}\\ =&\,\frac{\alpha^{n-2}\color{blue}{(1+\alpha)}-\beta^{n-2}\color{red}{(1+\beta)}}{\alpha-\beta}=\frac{\alpha^{n-2}\color{blue}{\alpha^2}-\beta^{n-2}\color{red}{\beta^2}}{\alpha-\beta}=\frac{\alpha^n-\beta^n}{\alpha-\beta}, \end{align*} where I used the fact that both $\alpha$ and $\beta$ solve $x^2-x-1=0$, so that $\color{blue}{\alpha^2=1+\alpha}$ and $\color{red}{\beta^2=1+\beta}$. Therefore, the induction goes through, as desired.

Answer 2

First, note that $\alpha - \beta = \sqrt 5$
We begin by confirming the relationship by $f_1,\ f_2$, once this has been confirmed, we need just the induction step.. $$f_{n+1} = f_n + f_{n-1} = \frac 1 {\sqrt 5}\left(\alpha^n + \alpha^{n-1} - \beta^n - \beta^{n-1}\right)$$ $$=\frac 1 {\sqrt 5}\left(\alpha^{n-1}\left(\alpha + 1\right) - \beta^{n-1}\left(\beta + 1\right)\right) = \frac1{\sqrt 5}\left(\alpha^{n+1} - \beta^{n+1}\right)$$ Because $\alpha + 1 = \alpha^2$ and $\beta + 1 = \beta^2$, so we are done.