# Recurrence relation

1. May 13, 2012

### dragonkiller1

$x_{xn-1}= 5_{xn-1} - 6_{xn-2};for \ n≥2 \\ x_{1}=1 \\ x_{0}=0$

prove by induction that:
$\begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} 1\\0 \end{bmatrix}$

2. May 13, 2012

### tiny-tim

welcome to pf!

hi dragonkiller1! welcome to pf!

show us what you've tried, and where you're stuck, and then we'll know how to help!

3. May 13, 2012

### dragonkiller1

I've showed the base step for n=1
For the inductive step:
Suppose P(k) is true for some k
$\begin{bmatrix} x_{k}\\ x_{k-1} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}^{k-1}\begin{bmatrix} 1\\0 \end{bmatrix}$
Then for n=k+1
$\begin{bmatrix} x_{k+1}\\ x_{k} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}^{k}\begin{bmatrix} 1\\0 \end{bmatrix}$
?
I'm stuck on the inductive step. >.<

4. May 13, 2012

### tiny-tim

hi dragonkiller1!

you obviously need to prove

$\begin{bmatrix} x_{n+1}\\ x_{n} \end{bmatrix} = \begin{bmatrix} 5 &-6 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} x_{n}\\ x_{n-1} \end{bmatrix}$

which is easier …

the top line or the bottom line?

5. May 13, 2012

### sk9

pre multiply 5,-6,1,0 matrix on both the sides(to the k equation) and you will have your proof

6. May 13, 2012

### dragonkiller1

Oh got it. Thanks :)