Solution to Fibonacci Recursion Equations

Question

Let the sequence $(a_n)_{n\geq0}$ of the fibonacci numbers: $a_0 = a_1 = 1, a_{n+2} = a_{n+1} + a_n, n \geq 0$

Show that:

i) $$a^2_n - a_{n+1}a_{n-1} = (-1)^n \text{ for }n\geq1$$ I try to show this with induction:

$n=1:$ \begin{align*} a^2_1 - a_{2}a_{0}&=1 - a_2a_0\\ &= 1- (a_1 + a_0 )a_0\\ &= 1-(1+1)1 = -1 = (-1)^1\\ \end{align*} Assume that: $a^2_n - a_{n+1}a_{n-1} = (-1)^n ,\forall n\geq1$

Inductive step: \begin{align*} a^2_{n+1} - a_{n+2}a_{n} &=(a_n + a_{n-1}) ^2 - (a_{n+1}+a_{n})(a_{n-1}-a_{n-2})\\ &=a^2_{n}+2a_na_{n-1}+a^2_{n-1}-a_{n+1}a_{n-1}+a_{n+1}a_{n-2}-a_{n}a_{n-1}+a_{n}a_{n-2}\\ &=(a^2_{n}-a_{n+1}a_{n-1})+(a^2_{n-1}-a_{n}a_{n-1})+2a_na_{n-1}+a_{n+1}a_{n-2}+a_{n}a_{n-2}\\ &=\underbrace{(-1)^n + (-1)^{n-1}}_{=0}+2a_na_{n-1}+a_{n+1}a_{n-2}+a_{n}a_{n-2}\\ &=2a_na_{n-1}+a_{n+1}a_{n-2}+a_{n}a_{n-2}\\ &=??\\ \end{align*}

ii) $$\sum \limits_{i=0}^na_i=a_{n+2}-1 , n\geq0$$

iii) $$a^2_{n-1}+a^2_n=a_{2n} \text{ and } a_{n-1}a_n+a_na_{n+1}=a_{2n+1}, n\geq1$$

Thank you for any help

Answer 1

Another flavor on the inductive step argument: $$ \begin{split} a_n^2-a_{n+1}a_{n-1} &= a_n^2-(a_n + a_{n-1})a_{n-1} \\ &= a_n^2 - a_n a_{n-1} - a_{n-1}^2 \\ &= a_n(a_n-a_{n-1}) - a_{n-1}^2 \\ &= a_n a_{n-2} - a_{n-1}^2 \\ &= -\left( a_{n-1}^2 - a_n a_{n-2}\right), \end{split} $$ reducing to the inductive hypothesis...

Answer 2

Since the first term of the induction process for part one has been established the t remains to be seen for general $n$. Now, \begin{align} a_{n+1}^{2} - a_{n} \, a_{n+2} &= a_{n+1}^{2} - a_{n} \, ( a_{n+1} + a_{n} )\\ &= a_{n+1} ( a_{n+1} - a_{n} ) - a_{n}^{2} \\ &= a_{n-1} \, a_{n+1} - a_{n}^{2} = (-1)^{n+1}. \end{align} This provides $a_{n}^{2} - a_{n-1} \, a_{n+1} = (-1)^{n}$.

For the second part: Using $a_{n} = a_{n+2} - a_{n+1}$ then \begin{align} \sum_{i=0}^{n} a_{i} &= \sum_{i=0}^{n} ( a_{i+2} - a_{i+1} ) = a_{n+2} - a_{1}. \end{align}

For the third part: Using the solution of the difference equation in the form $(\alpha - \beta) a_{n} = \alpha^{n} - \beta^{n}$ where $2 \alpha = 1 + \sqrt{5}$ and $2 \beta = 1 - \sqrt{5}$. Now, \begin{align} a_{n}^{2} + a_{n-1}^{2} &= \frac{1}{5} \left[ (\alpha^{2n} - 2(-1)^{n} + \beta^{2n}) + (\alpha^{2n-2} + 2 (-1)^{n} + \beta^{2n-2}) \right] = a_{2n-1}. \end{align}

For the fourth part: \begin{align} a_{n} ( a_{n+1} + a_{n-1} ) &= \frac{a_{n}}{\alpha - \beta} \, \left[ \alpha^{n} \left( \alpha + \frac{1}{\alpha} \right) - \beta^{n} \left( \beta + \frac{1}{\beta} \right) \right] \\ &= \frac{(\alpha^{n} - \beta^{n})(\alpha^{n} + \beta^{n})}{\alpha - \beta} \\ &= a_{2n}. \end{align}