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
    Well, there is $a$ more system$a$tic w$a$y to get $a$rbitrary 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