This should really be a comment to this answer but I don't have enough rep. I'd like to know how to do the same thing (efficiently - see below) but with $\mod 3$ conditions, i.e. define a[k] to be the $0\mod 3$ index terms of the function, b[k] (resp. c[k]) the $1\mod 3$ (resp. $2\mod 3$) indexes. Copying the method in the linked answer works for some simpler recursive formulas. However, for the more complicated formulas that I'm interested in, the process does not seem to stop, even given an hour + to run. What can I do about this?
Edit: Here's a more specific version of my question. I have something like the following recursive formula for a sequence $a_n$: $$a_n=\begin{cases} 3a_{n-1}+3^{n+3}:& n\not\equiv 1\mod 3\\ 3a_{n-1}+5\cdot 3^n:& n\equiv 1\mod 3 \end{cases}$$ and $a_1=1$. I want code that gives a closed form for $a_n$ (probably will be piecewise defined, that's fine). The answer that I linked does this for $\mod 2$ conditions, and anything higher seems to complicate matters so much that it doesn't terminate in time.
(x*(1 + 243*x + 729*x^2 + 378*x^3))/((-1 + 3*x)^2*(1 + 3*x + 9*x^2))
. First few terms are{1, 246, 1467, 4806, 20979, 82620, 258795}
. $\endgroup$t=seralgdep(A,1,4)
whereA = y + 246*y^2 + ... + 953532*y^8 + O(y^9)
andt=(81*y^4 - 27*y^3 -3*y + 1)*x + (-378*y^4 - 729*y^3 - 243*y^2 - y)
gives the rational form by solving $t=0$ for $x$ in terms of $y$. $\endgroup$