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.
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)\,$.
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.