= Exponential forcing in a linear recurrence
{title2=$P(E)y_n=r^n$}
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)\ne0$. At a simple root of the <characteristic equation of a linear recurrence>, the correct trial acquires a factor $n$:
$$
P(E)(nr^n)=r^n\bigl(nP(r)+rP'(r)\bigr),\qquad
y_n=\frac{nr^n}{rP'(r)}.
$$
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>.
Back to article page
