I have been working on a math question that someone asked me, and the following linear recurrence (base cases unspecified) came up:
$$ T_{n}=1/6(T_{n-1}+T_{n-2}+T_{n-3}+T_{n-4}+T_{n-5}+T_{n-6})+[rem(n,5)=r] $$
$r$ is a parameter of the recurrence that is an integer between $0$ and $4$, inclusive. And the term at the end is an Iverson bracket, which evaluates to $1$ if the condition inside is true and $0$ otherwise. Normally when solving linear recurrences, one looks for the homogeneous and inhomogeneous solutions to the recurrence. If you examine the characteristic polynomial of this equation and set it to $0$, you can figure out that if $T_{n} = a^{n}$ is a solution to the homogeneous variant of this equation, then $$(a - 1)*(6a^{5}+5a^{4}+4a^{3}+3a^{2}+2a+1)=0$$ However, I'm not sure if it is possible to factor this any further, and although I could get an approximate solution using a laptop I would prefer to have an exact answer.
Another issue is that we need the inhomogeneous solution to the recurrence. I guessed that the inhomogeneous solution could be a function whose output only depends on the input's remainder upon division by $5$, but I think this can't be the case. Let's say that such a function existed, which would mean that if $T_{n}$ is a solution to this inhomogeneous variant, then $T_{n}=s_{rem(n,5)}$ for some sequence of $5$ values s, and these values would have to satisfy the following system of equations: $$s_{0}=1/6(s_{4}+s_{3}+s_{2}+s_{1}+s_{0}+s_{4})+[0=r]$$ $$s_{1}=1/6(s_{0}+s_{4}+s_{3}+s_{2}+s_{1}+s_{0})+[1=r]$$ $$s_{2}=1/6(s_{1}+s_{0}+s_{4}+s_{3}+s_{2}+s_{1})+[2=r]$$ $$s_{3}=1/6(s_{2}+s_{1}+s_{0}+s_{4}+s_{3}+s_{2})+[3=r]$$ $$s_{4}=1/6(s_{3}+s_{2}+s_{1}+s_{0}+s_{4}+s_{3})+[4=r]$$ Adding all $5$ equations together tells us that: $$ s_{0}+s_{1}+s_{2}+s_{3}+s_{4} = s_{0}+s_{1}+s_{2}+s_{3}+s_{4} + 1 $$ There are $6$ copies of each $s_{i}$ on the right side so that will cancel with the $1/6$, and since $r$ is exactly one of the integers between $0$ and $4$, the sum of the Iverson bracket terms will be $1$. And this equation is obviously not solvable, since it says that something equals itself plus one.
So I'm pretty sure the inhomogeneous part must depends on more than just the remainder of the number, but I'm totally lost on what to try from here. Any help finding exact solutions to the homogeneous part (or verifying it's impossible to do so), solutions to the inhomogeneous part, or alternative techniques for finding a general solution to this recurrence would be helpful. Thanks!
Edit 1 I've realized that you can use generating functions to find an inhomogeneous solution to the linear recurrence. I won't go over exactly what I did here, but if I did it correctly then the solution to the recurrence corresponds to the coefficients of the power series following function (note that $T_{0}$ through $T_{5}$ are pre-defined base cases): $$ \frac{6x^{6+rem(r-1, 5)}+(1-x^{5})\Sigma_{i=0}^{5}(x^i(6T_{i}-\Sigma_{j=0}^{i-1}T_{j}))}{(1-x^5)(6-x-x^{2}-x^{3}-x^{4}-x^{5}-x^{6})} $$
From here all that's needed is partial fraction decomposition and I can give a closed form. Anyone know how to do that in this case? I'm guessing that it has to do with a smart choice of base cases (they can be anything since we only care about finding one inhomogeneous solution), but I'm not entirely sure. I'll work on this some more and update if I figure anything out.
Edit 2 Found the particular solution: $$T_{n}^{p}=\frac{2}{35}n+2(\frac{30(6cos(\frac{2\pi(n-r)}{5})-cos(\frac{2\pi(n-r+1)}{5}))}{925-300cos(\frac{2\pi}{5})}+\frac{30(6cos(\frac{4\pi(n-r)}{5})-cos(\frac{4\pi(n-r+1)}{5}))}{925-300cos(\frac{4\pi}{5})})$$ I realized that we don't actually need to do the partial fraction decomposition to find the solution. Examining the structure of the generating function that was found gives us a hint as to what form the particular solution should have. Note that whenever we do partial fraction decomposition, we break the polynomial in the denominator into its factors. The roots of $6-x-x^{2}-x^{3}-x^{4}-x^{5}-x^{6}$ will lead to the homogeneous solutions as mentioned previously, so the roots of the new factor in the denominator $1-x^5$ will (probably?) lead to the particular solution. The roots of this equation are all $x$ satisfying $1=x^{5}$, which are the 5th roots of unity, represented in polar form as $e^{2\pi ik/5}$ for integers k between 0 and 4. Note that one of these roots is 1, which corresponds to the homogeneous solution, so by the rules for solving linear recurrences we multiply by n to get the particular solution. This suggests that we should try guessing that our particular solution will have the form $$T_{n}^{p}=an+\Sigma_{n=1}^{4}(c_{j}*e^{2\pi ik/5})$$ For some set of coefficients a and $c_{1}$ through $c_{4}$. It may be suprising to find that the generating function indicates the particular solution should be of this form, given that the inhomogeneous part of this recurrence, namely the Iversonian bracket, looks nothing like that. But as a matter of fact, the function [rem(n,5)=r] can be rewritten in terms of the 5th roots of unity: $$[rem(n,5)=r]=\frac{1}{5}\Sigma_{k=1}^{5}e^{2\pi ik(n-r)/5}$$ This is because the roots of unity sum to 0, and as long as (n-r) isn't a multiple of 5, raising the 5th roots of unity to the same power will reproduce all of the roots of unity, leading the sum to remain 0. However, when (n-r) is a multiple of 5, it is equivalent to raising all the 5th roots of unity to a power of 5 which by definition will give 1, so the sum will sum one 5 times, giving 5/5 = 1. Using this trick, and after a lot of algebra and Euler's formula expansions, you can obtain the particular solution I found.
This reminds me a lot of 3blue1brown's video on solving the Olympiad problem with generating functions and complex numbers (https://www.youtube.com/watch?v=bOXCLR3Wric), in the sense that in both cases, there is a problem that initially appears to have nothing to do with complex numbers that somehow shares an intimate link with them because of their mutual periodicity. One of the many reasons I love mathematics.
Now that I have a particular solution, I can now get an approximate full closed form, and may share that here later, but if anyone knows any ways to get exact homogeneous solutions in this case please let me know.
