How to show that closed form of Fibonacci number is roots ratio difference of $n^{th}$ power of roots to difference of roots of $x^2 - x - 1=0$

1.5 The Fibonacci numbers $1,1,2,3,5,...$ are defined by the recursion formula $x_{n+1} = x_n + x_{n-1}$, with $x_1 = x_2 = 1$. Prove that $(x_n, x_{n+1}) = 1$ and that $x_{n} = \frac{a^n -b^n}{a-b}$ where $a,\text{and }b$ are roots of quadratic equation $1 +x-x^2=0$.

I just need help here $x_{n} = \frac{a^n -b^n}{a-b}$

-
–  lhf Dec 18 '12 at 10:18

HINT: Let $$a=\frac{1+\sqrt5}2\quad\text{and}\quad b=\frac{1-\sqrt5}2\;,$$ the two roots of $1+x-x^2=0$.

1. Show that if $A$ and $B$ are arbitrary constants, and we define a sequence $\langle u_n:n\in\Bbb N\rangle$ by $u_n=Aa^n+Bb^n$, then the sequence satisfies the recurrence $u_n=u_{n-1}+u_{n-2}$, just like the Fibonacci numbers. (In fact every sequence satisfying the Fibonacci recurrence can be obtained in this way by a suitable choice of $A$ and $B$.

2. Now use the known values of $x_1$ and $x_2$ to set up the system \left\{\begin{align*}&x_1=Aa+Bb\\&x_2=Aa^2+Bb^2\end{align*}\right. and solve for $A$ and $B$.

3. Substitute the values of $A$ and $B$ from step (2) into the equation $u_n=Aa^n+Bb^n$; on the one hand you can show by induction that $u_n=x_n$ for all $n$, and on the other hand $Aa^n+Bb^n$ will be the desired function of $a$ and $b$ (if you’ve made no algebra errors along the way).

-

To prove that $(x_{n+1},x_n)=1$, we will use induction. The base is easy to verify. Now comes the step.

Since $(x_{n+1},x_n)=1$, therefore $ax_{n+1}+bx_{n}=1$ for some $a,b\in Z$. Since $x_{n+2}=x_{n+1}+x_n$, therefore $bx_{n+2}=bx_{n+1}+bx_n=bx_{n+1}+1-ax_{n+1}$. Thus, $bx_{n+2}+(a-b)x_{n+1}=1$. Hence $(x_{n+2},x_{n+1})=1$

-

The characteristic polynomial will be $t^2-t-1=0\implies ab=-1$ and $b^2-b-1=a^2-a-1=0$

So, $x_n=Aa^n+Bb^n$

$\implies 1=x_1=Aa+Bb$

and $1=x_2=Aa^2+Bb^2$

Solve for $A,B$

$A=\frac{b^2-b}{ab(b-a)}=\frac1{a-b}$

Similarly, $B=-\frac1{a-b}$

$(x_{n+1},x_n)=(x_n+x_{n-1},x_n)=(x_{n-1},x_n)=(x_n,x_{n-1})=\cdots=(x_2,x_1)=1$

-