1
$\begingroup$

I was given the following as an example of a linear recurrence and I don't understand how it works...

Let us call the following eq1: $$x_i = \begin{bmatrix} \sum_{z = 1}^i{zk^{z-1}} \\ (i+1)k^i \\ k^i \end{bmatrix}$$

And the following eq2:

$$ x_{i+1} = \begin{bmatrix} 1 & 1 & 0 \\ 0 & k & k \\ 0 & 0 & k \end{bmatrix}x_i $$

Given eq1, by what steps, method or algorithm can you derive eq2?

Likewise for the reverse, by what method can you derive eq1 from eq2?

1 Answers 1

1

Given equation 1, replace $i$ everywhere by $i+1$ to get an equation for $x_{i+1}$, then in equation 2 substitute the value of $x_i$ from equation 1, and the value of $x_{i+1}$ just derived, and do the matrix multiplication, and see what you get. If what you get is stuck, come back for more help.

Given equation 2, probably the best way to get equation 1 is by induction, but that doesn't show you where it comes from. So, instead, let $x_1=(1,2k,k)$ (or maybe let $x_0=(0,1,1)$) and use equation 2 to find $x_2$ and $x_3$ and $x_4$ and however many more you need to start seeing the pattern, which ought to be the pattern given in equation 1. Then you can do a proof by induction.

  • 0
    So thanks, but I think my question wasn't completely clear. Given __both__ eq1 and eq2, it is easy to verify by substitution they are equivilant. My question was if you are only given __one__, how do you derive the other form. You have partially suggested an answer of eq2->eq1 by writing out the first few terms of the series and then "guessing the pattern", I thought there were more precise methods than that.2012-06-07
  • 0
    Well, there is a more systematic way to get arbitrary powers of given matrices, involving computing the eigenvalues and eigenvectors, and you can use that instead to go from (2) to (1).2012-06-07