<s>[INST] Solving recursive formula dependent on a periodic function Say we have some initial values $a_1, a_2, \dots, a_k$ and a recursive formula $a_n = f(n) + c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k}$ Where $f(n)$ is periodic and $a_n,f(n),c_i \in \mathbb{N}$.
For example let $a_1 = 1$ and $a_n = f(n) + 2a_{n-1}$ where $f(n) = 1,2,1,2 \dots$
How can we generally solve this kind of formula?
I was initially thinking to solve the linear recurrence relation for each value of $f(n)$ and then merge the subsequences, but not sure how this should be done. The main issue is how to describe the extra shifting done each time we get a higher value for $f(n)$
In the example we can solve $a_{n,1} = 1 + 2a_{n-1,1}$ and get $a_{n,1} = 2^n - 1$
And solve $a_{n,2} = 2 + 2a_{n-1,2}$ and get $a_{n,2} = 3\cdot2^{n-1} - 2$
Though I am not sure how to merge them to get $a_n$ which first values are $a_n= 1, 3, 8, 17, 36,..$ given by multiplying by $2$ and adding $1$ or $2$ alternately.
 [/INST] Suppose $\,f(n)\,$ has period $\,K\,$, then eliminating $\,f(n+K)=f(n)\,$ between the two recurrence relations for $\,a_n+K\,$ and $\,a_n\,$ gives a linear homogeneous recurrence that no longer includes $\,f(n)\,$, which can be solved with the usual methods.
$$
\begin{cases}
\begin{align}
a_{n+K} &= f(n+K) + c_{1}a_{n+K-1} + c_{2}a_{n+K-2} + \dots + c_{k}a_{n+K-k}
\\ a_n &= f(n) + c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k}
\end{align}
\end{cases}
$$
$$
\begin{align}
\implies\quad\quad a_{n+K} = a_n &+ (c_{1}a_{n+K-1} + c_{2}a_{n+K-2} + \dots + c_{k}a_{n+K-k}) \quad\quad\quad\quad\quad\quad
\\ &- (c_{1}a_{n-1} + c_{2}a_{n-2} + \dots + c_{k}a_{n-k})
\end{align}
$$
It can be shown that if the characteristic polynomial of the original recurrence is $\,p(t)\,$ then the characteristic polynomial of the derived recurrence is $\,(t^K-1)\,p(t)\,$.

For example let $a_1 = 1$ and $a_n = f(n) + 2a_{n-1}$ where $f(n) = 1,2,1,2 \dots$

This is the case $\,k=1\,$, $\,p(t)=t-2\,$, $\,K=2\,$.
$$
\begin{cases}
\begin{align}
a_{n+2} &= f(n+2) + 2a_{n+1}
\\ a_n &= f(n) + 2a_{n-1}
\end{align}
\end{cases}
$$
$$
\implies\quad\quad a_{n+2} = 2a_{n+1} + a_n  - 2a_{n-1} \quad\quad\;\;
$$
The characteristic polynomial is $\,t^3-2t^2-t+2 = (t^2-1)(t-2)\,$, with roots $\,\pm 1, 2\,$, so $\,a_n = C_1 + C_2 \,(-1)^n + C_3 \,2^n\,$ where $\,C_1,C_2,C_3\,$ are determined from the initial conditions.
</s>