0

This problem is from Chapter 1, Probiem 8 (1st edition) of Apostol's Mathematical Analysis.

Let $a,b$ denote the roots of the quadratic equation $x^2-x-1=0$, and let $x_n=\frac{a^n-b^n}{a-b}$. Show that $x_{n+1}=x_n+x_{n-1}$.

The roots of the quadratic are $\frac{1\pm\sqrt 5}{2}$. We can write $x_n = \frac{a^n-b^n}{a-b}=\sum_{j=0}^{n-1}a^jb^{n-1-j}$, and there are similar looking sums for $x_{n-1},x_{n+1}$. However, I'm unsure of why the sums for $x_n$ and $x_{n-1}$ are the same as the sum for $x_{n+1}, $ and I am unsure of how to use the fact that $a,b$ are roots of $x^2-x-1$.

Iced Palmer
  • 755

2 Answers2

1

We know that $a,b \neq 0$ and that $a\neq b$ so we can write:

$$x_{n+1}=x_n+x_{n-1} \rightarrow \frac{a^{n+1}-b^{n+1}}{a-b}=\frac{a^{n}-b^{n}}{a-b}+\frac{a^{n-1}-b^{n-1}}{a-b}$$

and we can multiply by $a-b (\neq 0)$ $$a^{n-1}(a^2-a-1)-b^{n-1}(b^2-b-1)=0$$ the last equation is verified since both $a^2-a-1$ and $b^2-b-1$ are equal to $0$ (here we are using the fact that they are solutions of the equation).

chak
  • 599
  • 1
  • 3
  • 7
0

Hint: $\,a^2=a+1\,$, $b^2=b+1\,$, and we can assume WLOG that $\,a\,$ is the positive root (since the expression is symmetric in $\,a,b\,$), so $\,a-b=\sqrt{5}\,$, then:

$$ x_{n+1}=\dfrac{1}{\sqrt{5}}\left(a^2 \cdot a^{n-1}-b^2\cdot b^{n-1}\right)=\dfrac{1}{\sqrt{5}}\left((a+1) \cdot a^{n-1}-(b+1)\cdot b^{n-1}\right)=x_n+x_{n-1} $$

[ EDIT ]   This is, of course, just the method of characteristic polynomials for linear homogeneous recurrences. In the general case, let $a_j \ne 0$ be a root of $p(t)=t^k-c_1t^{k-1}-c_2t^{k-2}-\ldots-c_k\,$ then multiplying the equality $p(a_j)=0$ by $a_j^n$ gives $a_j^{n+k}=c_1 a_j^{n+k-1}+c_2a_j^{n+k-2}\ldots+c_ka_j^n\,$, so the sequence $x_n=a_j^n$ satisfies the recurrence $x_{n+k}=c_1x_{n+k-1}+c_2 x_{n+k-2}+\ldots+c_kx_n\,$.

Furthermore, it follows by linearity that if $x_n$ and $x_n'$ both satisfy the respective recurrence, then so does any linear combination $x_n''=\lambda x_n+\mu x_n'\,$, so in the end any linear combination of the form $\,x_n = \lambda_1a_1^n+\lambda_2a_2^n+\ldots +\lambda_ka_k^k\,$ satisfies the same recurrence.

OP's problem is the particular case $p(t)=t^2-t-1$ with $a=a_1\,$, $b=a_2\,$, $\lambda_1=\frac{1}{a-b}\,$, $\lambda_2=\frac{-1}{a-b}\,$.

dxiv
  • 76,497