recurrence relation of a finite sequence 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$?

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. 
