1
$\begingroup$

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$?

$\endgroup$
1
  • $\begingroup$ are you familiar with generating functions? $\endgroup$
    – Alex
    Sep 4, 2014 at 18:20

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I often work with infinite sequences so that if the recurrence relation is satisfied for $k \ge 1$ then we can deduce the general formula for $v_k, k \ge 1$. What happens if the relation is just satisfied for finite numbers $k$ for instance here $k=1,2,\ldots,n-2$? $\endgroup$
    – user
    Sep 4, 2014 at 18:30
  • $\begingroup$ Please read more carefully. You want the general term, right? $\varphi(n)$ is your general term. Whether the original recurrence is finite or not doesn't matter. $\endgroup$
    – Alex
    Sep 4, 2014 at 18:35
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you @Mark Bennet. Nice explanation. That means even the recurrence relation is true for finite numbers $k$ we can still have the general formula for $v_k$, isn't it? $\endgroup$
    – user
    Sep 5, 2014 at 2:49
1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Your answer is very easy to follow, @amcalde thank you. Btw, what is the range of $k$ in your formula of $v_k$? I wonder $k=1,2,\ldots,n$ or $k \ge 1$? $\endgroup$
    – user
    Sep 5, 2014 at 2:53
  • $\begingroup$ Well it only works for $3 \le k$ as that is when the recursion actually kicks in. So yeah, $k\ge 3$. $\endgroup$
    – amcalde
    Sep 5, 2014 at 3:47
  • $\begingroup$ If I assume the characteristic equation $x^2-ax-b=0$ has two different roots $x_1,x_2$ can I deduce that $v_{k}=Ax_1^k+Bx_2^k, k=1,2,\ldots,n$? $\endgroup$
    – user
    Sep 5, 2014 at 15:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .