0
$\begingroup$

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}$

  • 0
    See http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression.2012-12-18

3 Answers 3

4

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).

2

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$

2

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$