Proving Recurrence Relation by Induction

[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}<br /> x_{n}\\ x_{n-1} <br /> \end{bmatrix} = \begin{bmatrix}<br /> 5 &amp;-6 \\ <br /> 1 &amp; 0<br /> \end{bmatrix}^{n-1}\begin{bmatrix}<br /> 1\\0 <br /> \end{bmatrix}

 

[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!

 

[dragonkiller1]

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

 

[tiny-tim]

hi dragonkiller1!

you obviously need to prove

\begin{bmatrix}<br /> x_{n+1}\\ x_{n} <br /> \end{bmatrix} = \begin{bmatrix}<br /> 5 &amp;-6 \\ <br /> 1 &amp; 0<br /> \end{bmatrix}\begin{bmatrix}<br /> x_{n}\\ x_{n-1} <br /> \end{bmatrix}

which is easier …

the top line or the bottom line? ​

 

[sk9]

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

 

[dragonkiller1]

Oh got it. Thanks :)