Inhomogeneous linear recurrence (${\sum }_{j=0}^k{a}_j{y}_{n+j}=g_n$)

An inhomogeneous linear recurrence has a prescribed forcing sequence $g_n$ rather than zero on the right. The difference of two solutions satisfies the associated homogeneous linear recurrence relation, so every solution is a particular solution plus a homogeneous solution.

The unit-response sequence $a_1=a_2=1$, $a_{n+2}-a_{n+1}+a_n=0$ is six-periodic. In the displayed convolution, all older terms cancel under $P_{k+2}-P_{k+1}+P_k$ by this recurrence; the two new boundary terms reduce to $f_{k+2}$. Thus it gives a particular solution of the inhomogeneous linear recurrence with forcing $f_{k+2}$. Add the two-dimensional homogeneous span of $\cos (k\pi /3)$ and $\sin (k\pi /3)$ for the general solution. This is a discrete Green function construction.

Let $E$ be the forward shift on sequences and $P$ the polynomial defining a constant-coefficient linear recurrence relation. For a nonzero base $r$, $P(E)r^n=P(r)r^n$, so $r^n/P(r)$ is a particular solution when $P(r)\ne 0$. At a simple root of the characteristic equation of a linear recurrence, the correct trial acquires a factor $n$:The identity follows by substituting $(n+j)r^{n+j}$ into each shift term. A root of multiplicity $m$ analogously requires a degree-$m$ polynomial factor; the lower-degree homogeneous terms are supplied by the repeated characteristic root of a linear recurrence.