recurrence relation of a finite sequence

Question

Suppose I have a sequence of vectors $v_1,v_2,\ldots,v_n$ and for $k=1,2,\ldots,n-2$ $$v_{k+2}=av_{k+1}+bv_k, \quad a,b\in \mathbb R.$$ Can I deduce that $v_{k}=Ax_1^k+Bx_2^k, k=1,2,\ldots,n$ in which $x_1,x_2$ are roots of the characteristic equation $t^2-at-b=0$ and $A,B$ are vectors can be determined by initial vectors $v_1,v_2$?

Answer 1

To be more fundamental, multiply both sides by $z^k$ and sum over $k$, the rightmost term will be $aG(z) = a\sum_{k=0}^{\infty} a_k z^k$. Do a bit of algebra with the other two to get $G(z)$, then get this term on LHS and everything else on the RHS. Do a bit more algebra and then on the RHS you'll have an expression of the form $\sum_{k=0}^{\infty} \varphi(k) z^k$. Equate coefficients for $z^n$, and $\varphi(n)$ will be your solution.

Answer 2

If the two roots are equal this will not work as stated.

Generally two consecutive values obviously determine the whole sequence. So if you have two sequences which agree at two consecutive places and satisfy the recurrence, they will agree at every other place.

Answer 3

Your recurrance can be written:

$\left(\begin{array}{c}v_{k+2} \\v_{k+1}\end{array} \right)= \left(\begin{array}{cc} a & b \\ 1 & 0\end{array}\right)\cdot \left( \begin{array}{c} v_{k+1} \\v_k\end{array} \right) $

So we can write this as

$\left(\begin{array}{c}v_{k+2} \\v_{k+1}\end{array} \right)= \left(\begin{array}{cc} a & b \\ 1 & 0\end{array}\right)^{k}\cdot \left( \begin{array}{c} v_{2} \\v_1\end{array} \right) $

To exponentiate the matrix you do indeed solve the equation that you post (the eigenvalues for the matrix obey that equation). You basically need to diagonalized the matrix (not too hard) and then exponentiate the eigenvalues.

I get: $v_k = \frac{\left(\frac{1}{4} X_+ X_-^{k+1}-\frac{1}{4} X_- X_+^{k+1}\right) v_1+ \left(\frac{1}{2}X_+^{k+1}-\frac{1}{2}X_-^{k+1}\right) v_2}{2^{k-1} (X_+ + X_-)}$

where $X_\pm$ are the said roots.