Solving a set of linked recurrent relations

235 Views Asked by At

I'm trying to find a method how to solve this set of linked recurrent relations.

$$ \left\{\begin{matrix} a_{n} = 3*a_{n-1} + b_{n-1}\\ b_{n} = 2*a_{n-1} + 2*b_{n-1}\\ c_{n} = b_{n-1} + 3*c_{n-1}\\ d_{n} = a_{n-1} + 2*b_{n-1} + 3*c_{n-1}\\ e_{n} = 6*d_{n-1} + 3*e_{n-1} + f_{n-1}\\ f_{n} = 2*e_{n-1} + 2*f_{n-1}\\ g_{n} = f_{n-1} + 3*g_{n-1}\\ \end{matrix}\right. $$

From what I've seen one method is to end up with recurrent relation only with one term: $a_{n}=c_{1}*a_{n-1}+c_{2}*a_{n-2}+...+c_{k}*a_{n-k}$ and then I can reduce the relation and find out the characteristic equation $r^{n}=c_1*r^{n-1}+c_2*r^{n-2}+...+c_k*r^{n-k}$.

I need to calculate $X_{n}=a_{n}+b_{n}+c_{n}$ and $Y_{n}=d_{n}+e_{n}+f_{n}+g_{n}$ so basically only if I can have a recurrent relation in one term separately I probably could apply that method.

Is there a simpler method to find this ?

1

There are 1 best solutions below

8
On BEST ANSWER

It's not quite clear to me if this is equivalent to the method you suggested but in the case of nice, linear recurrences like you have, one can write:

$$ \vec{x}_n = \begin{pmatrix}a_n\\b_n\\c_n\\d_n\\e_n\\f_n\\g_n\end{pmatrix} = \begin{pmatrix}3 & 1 & 0 & 0 & 0 & 0 & 0 \\ 2 & 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 3 & 0 & 0 & 0 & 0 \\ 1 & 2 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 6 & 3 & 1 & 0 \\ 0 & 0 & 0 & 0 & 2 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 3 \end{pmatrix} \begin{pmatrix}a_{n-1}\\b_{n-1}\\c_{n-1}\\d_{n-1}\\e_{n-1}\\f_{n-1}\\g_{n-1}\end{pmatrix} = A \vec{x}_{n-1}$$

and thus compute

$$ \vec{x}_n = A^n \vec{x}_0.$$

If you let $M = S J S^{-1}$ as the Jordan normal form of $M$, you can compute

$$ \vec{x}_n = S J^n S^{-1} \vec{x}_0$$

rather quickly as $J$ will only have nonzero elements on the diagonal and superdiagonal.

Performing the computations myself gives

$$ S^{-1} \vec{x}_0 = \begin{pmatrix}0\\-2\\-2\\54\\36\\-56\\24\end{pmatrix}$$

and so

$$ J^n S^{-1} \vec{x}_0 = \begin{pmatrix}0\\-2\\-2\\54 \cdot 3^n + 36 \cdot n \cdot 3^{n-1}\\36 \cdot 3^n\\-56 \cdot 4^n + 24 \cdot n \cdot 4^{n-1}\\24\cdot 4^n\end{pmatrix}$$

so finally we have

$$ \vec{x}_n = S J^n S^{-1} \vec{x}_0 = \begin{pmatrix} 2 + 4^{n+1}\\ 4^{n+1} - 4\\ 2 + 4^{n+1}-6\cdot 3^n\\ 6(4^n - 3^n) \\ 2 + 18 \cdot 3^n -56 \cdot 4^n + 24 \cdot n \cdot 4^{n-1} + 36 \cdot 4^n\\ -4 + 36 \cdot 3^n -56 \cdot 4^n + 24 \cdot n \cdot 4^{n-1} + 24 \cdot 4^n\\ 2 + 54 \cdot 3^n + 36 \cdot n \cdot 3^{n-1} -56 \cdot 4^n + 24 \cdot n \cdot 4^{n-1} \end{pmatrix}$$

Putting it all together gives

$$ X_n = a_n + b_n + c_n= 6[2\cdot 4^n - 3^n]$$

as you noted, and

$$ Y_n = d_n + e_n + f_n + g_n = 6[4^n(3n-17)+3^n(2n+17)].$$

So $Y_1 = 6$ according to the formula, which matches hand computation. If you have some further values computed, it would be nice to verify, but this at least passes an initial "sniff test".

Now that I think about it, this could have been done a lot more simply by solving for $a_n$, $b_n$, and $c_n$ explicitly using the matrix method and then using the resulting solution for $d_n$ to solve the rest.