2

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 ?

  • Please see my latest revision. What is this problem for, out of curiosity? – Nitin Nov 18 '16 at 00:43
  • @Nitin Sorry for the delay. I just saw the question now when I wanted to give it another try. All this is for https://projecteuler.net/problem=570 but I think that I need to learn more maths to crack it. A brute force approach doesn't quite cut it. – mihaipopescu Sep 05 '17 at 22:05

1 Answers1

3

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.

Nitin
  • 2,948
  • I will try this approach. Thanks. – mihaipopescu Nov 15 '16 at 09:52
  • Also, using another approach to my initial problem I ended up having $X_n=6{X_{n-1}-\sum_{k=n-2}^1{X_k}}$ with $X_0=1$ and for this I've found the sequence to be http://oeis.org/A255463 which apparently solves to $X_n=34^n-2*3^n$. – mihaipopescu Nov 15 '16 at 10:00
  • I've just tried it with the first three relations with $$ J=\left(\begin{matrix} 1 & 0 & 0\ 0 & 3 & 0\ 0 & 0 & 4\ \end{matrix}\right) $$ and ended up with $X_n=6(2*4^n-3^n)$. So the rest is just about crunching numbers for the big matrix. – mihaipopescu Nov 15 '16 at 20:23
  • Yeah, I think it should be possible to find a closed form for the matrix $J^n$ but I'm not sure. Hope this helped. – Nitin Nov 15 '16 at 20:26
  • With the Jordan normal form https://www.wolframalpha.com/input/?i=JordanDecomposition%5B%7B%7B3,+1,+0,+0,+0,+0,+0%7D,+%7B2,+2,+0,+0,+0,+0,+0%7D,+%7B0,+1,+3,+0,+0,+0,+0%7D,+%7B1,+2,+3,+0,+0,+0,+0%7D,+%7B0,+0,+0,+6,+3,+1,+0%7D,+%7B0,+0,+0,+0,+2,+2,+0%7D,+%7B0,+0,+0,+0,+0,+1,+3%7D%7D%5D and $x_0=(6,0,0,0,0,0,0)$ I end up with the correct formula for $X_n$ but for the rest $Y_n < 0$ which is not correct. I've run the calculations several times, same result. I could be doing something wrong... – mihaipopescu Nov 17 '16 at 22:19
  • Also, if I compute only the first 4 relations the method seems to work. I found that $d_n=32^{1+2n}-2*3^{1+n}$ which matches with a series that I had before. The problem is that apparently something happens when I'm computing the normal of the 7x7 matrix. What do you mean by a closed form for the matrix $J^n$ ? – mihaipopescu Nov 17 '16 at 22:56
  • See my edit. I computed $X_n$ and $Y_n$, and the value for $Y_1$ is positive and matches hand computation. – Nitin Nov 18 '16 at 00:35
  • I think I messed the last multiplication with S $\vec{x}_n=S*(J^nS^{-1}\vec{x}_0)$. Thanks a lot ! It's awesome ! – mihaipopescu Nov 18 '16 at 10:34