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