Finding a closed form for $x_0 = c_0, x_1 = c_1, \dots, x_{m-1} = c_{m-1}$ with $x_{n} = ax_{n-m} + b$ I've seen many explanations for finding a closed form by unrolling the sequence, guessing a pattern and then proving by induction.
Though, if we have many initial values this method becomes less handy.
Is there a way to calculate a closed form for this general structure?
$x_0 = c_0, x_1 = c_1, \dots , x_{m-1} = c_{m-1}$ and $x_{n} = a \cdot x_{n-m} + b$
 A: The unrolling you described works well in this case too, we can see
$$
x_n=ax_{n-m}+b=a(ax_{n-2m}+b)+b=\dots=a^k x_{n-km}+b(a^{k-1}+\dots+a+1)
$$
which can be proven inductively (as long as $n-km \geq 0$). Then based on remainder of $n$ modulo $m$ we can see that $n-km=c_i$ for exactly one value of $0 \leq i < m$ (specifically $i=n \bmod m$). Indeed we have $n=\lfloor n/m \rfloor \cdot m+ (n \bmod m)$, so if we choose $k=\lfloor n/m \rfloor$ we have
$$
x_n=a^{\lfloor n/m \rfloor}c_{n \bmod m}+b(a^{\lfloor n/m \rfloor-1}+\cdots+a+1 ).
$$
This can be further simplified using formula for sum of geometric series for $a \neq 1$ (and it is even simpler with $a=1$).
A: Yes, generating functions(If you are not familiar, is a machine to record recursions in a compact way). I am going to assume $a\neq 1,$ otherwise you do not even have a recursion.What you do is consider the formal series $$X(y)=\sum _{n = 0}^{\infty}x_ny^n,$$
by your assumption you have that
$$X(y)=\left (\sum _{n=0}^{m-1}c_ky^k\right )+\sum _{n=m}^{\infty}x_ny^n=\left (\sum _{n=0}^{m-1}c_ky^k\right )+\sum _{n=m}^{\infty}\left (a\cdot x_{n-m}+b\right )y^n,$$
being formal you do not worry of convergence or anything and so you can split sums and multiply as you which.
$$X(y)=\left (\sum _{n=0}^{m-1}c_ky^k\right )+a\sum _{n=m}^{\infty}x_{n-m}y^n+b\sum _{n=m}^{\infty}y^n=\left (\sum _{n=0}^{m-1}c_ky^k\right )+ay^m\sum _{n=m}^{\infty}x_{n-m}y^{n-m}+\frac{by^m}{1-y},$$
$$X(y)=\left (\sum _{n=0}^{m-1}c_ky^k\right )+ay^mX(y)+\frac{by^m}{1-y},$$
so
$$(1-ay^m)X(y)=\left (\sum _{n=0}^{m-1}c_ky^k\right )+\frac{by^m}{1-y},$$
$$X(y)=\frac{1}{1-ay^m}\left (\sum _{n=0}^{m-1}c_ky^k\right )+\frac{by^m}{(1-ay^m)(1-y)}$$
$$X(y)=\left (\sum _{n=0}^{\infty}a^ny^{n\cdot m}\right )\left (\sum _{n=0}^{m-1}c_ky^k\right )+by^m\left (\sum _{n=0}^{\infty}a^ny^{m\cdot n}\right )\left (\sum _{j=0}^{\infty}y^j\right ),$$
notice that in the first term the exponent of $y$ has the form $n\cdot m+k$ which by the divison algorithm tells you that if you want $x_n$
you have to divide $n$ by $m$ getting $n=m\cdot \lfloor \frac{n}{m}\rfloor+(n\pmod m),$ where $n\pmod m$ is the remainder of the division, so $$x_n = c_{n\pmod m}a^{\lfloor \frac{n}{m}\rfloor}+\text{the contribution of the second term},$$

In the second term we have a convolution of two series, notice that we are going to start at $m,$ so we can make this explicit using Iverson bracket $[n\geq m]$ which is $1$ if the proposition is true. So notice that the contribution of the exponents looks like $m+j+m\cdot k=n$ so when $j=0$ you get $m(k+1)=n$ hence $k=\lfloor \frac{n}{m}\rfloor -1$ and if $j=n-m$ we get $k=0$ so we have to add all these terms $a^0,a^1,\cdots a^{\lfloor \frac{n}{m}\rfloor -1}$ multiplied to $b$ and so the expressions ends up being
$$x_n = c_{n\pmod m}a^{\lfloor \frac{n}{m}\rfloor}+[n\geq m]\cdot b\cdot (a^{\lfloor \frac{n}{m}\rfloor -1}+\cdots +a +1)$$
$$x_n=c_{n\pmod m}a^{\lfloor \frac{n}{m}\rfloor}+[n\geq m]\cdot b\cdot \frac{a^{\lfloor \frac{n}{m}\rfloor}-1}{a-1}.$$
I was answering and Sil posted first (+1). Sorry for the inconvenience if this is redundant but it took me a while to write it down.
