This is a follow-on question to my previous one:
All the different ways to add a set of lengths - need explanation of the answer
I have a problem simplifying a specific recursion relation. I have trouble understanding some of the steps.
The general recursion relation (which I do understand) is:
$$r_1 = s_1$$
$$r_2 = s_2 + s_1 r_1$$ $$r_3 = s_3 + s_2 r_1 + s_1 r_2$$ $$r_4 = s_4 + s_3 r_1 + s_2 r_2 + s_1 r_3$$
It it gives the number of different ways $r_n$ of making a total length $n$ by summing a number of smaller or equal lengths $s_n$ where the $s_n$ are unique. For example, if we are making a length $n$ of boards end-to-end, and there are two different types of boards of length 3, then $s_3=2$.
In this particular case, discussed in OEIS A134438 (Kreweras), $s_1, s_2, ... = 1,2,5,2,2,4,2,2,4,2,2,4...$
To collapse the infinite recursion of $r_n$, generating functions $R(t)$ and $S(t)$ are used.
The statement is made: the $t^i$ coefficient of $R(t)$ is the the same as the $t^i$ coefficient of $R(t)[S(t)-1]$ However, I would instead expect: $R(t)$ has the same coefficient as $S(t)[R(t)-1]$. Is there a typo in the paper? It is then said that since $R(t) = [2- S(t)]^{-1}$, and since the S(n) soon start repeating mod(3), we have: $$S(t) = [1 + t + 2t^2 + 4t^3 +t^4 - t^6] [1-t^3]^{-1}$$ and
$$R(t) = [1-t^3] [1 - t - 2t^2 - 6t^3 - t^4 + t^6]$$ so $$r_n = r_{n-1} + 2r_{n-2} + 6 r_{n-3} + r_{n-4} - r_{n-6}$$
I am having trouble filling in the intermediate steps. I think the general method is to identify the coefficients of the power series for $S(t)$ as the sum of partial fractions of the form $1/(1-t)$ (or here, $1/(1-t^3)$) along with coefficients found from the known cyclic values, and equate each $r_n$ coefficient in of $r_n t^n$ in $R(t)$ to the sum of the $(r_{n-1},...,r_{n-6})$ values, as shown.
The paper I am looking at is translated here stevelord.net/13729kreweras.pdf
I do understand a second solution method is to do arithmetic on the recursion directly: $$()=(−1)+2(−2)+5(−3)+2(−4)+2(−5)+4(−6)+2(−7)+2(−8)+4(−9)+....$$ subtract from this: $$(−3)=(−4)+2(−5)+5(−6)+2(−7)+2(−8)+4(−9)+....$$ to get, $$r(n)-r(n-3) = [r(n-1) + 2 r(n-2) + 5 r(n-3) + 2 r(n-4) + 2 r(n-5) + 4 r(n-6)] - [r(n-4) + 2 r(n-5) + 5 r(n-6)]$$ to get finally, $$r(n) = r(n-1) + 2 r(n-2) + 6 r(n-3) + r(n-4) - r(n-6)$$
But, how this is done via generating functions? Thanks.