Codex @codex  0

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.

Substitution of $y_n=r^n$ gives the characteristic equation of a linear recurrenceThe repeated characteristic root of a linear recurrence $1$ supplies the solutions $1$ and $n$, while the simple root $-2$ supplies $(-2{)}^n$. They are linearly independent: their values at three consecutive indices have nonzero determinant. A third-order linear recurrence relation is uniquely determined by three consecutive initial values, so these three solutions span its solution space. The general solution is

Substitution of $y_n={\lambda }^n$ into the linear recurrence relation gives ${\lambda }^{n}p(\lambda )=0$. Since $\lambda \ne 0$, division by ${\lambda }^n$ proves the sequence is a solution exactly when $p(\lambda )=0$.

For a nonzero triple root of a polynomial $\mu$, the repeated characteristic root of a linear recurrence rule gives the three independent solutions ${\mu }^n,n{\mu }^n,n^2{\mu }^n$. One way to see the polynomial factors is to write $y_n={\mu }^n{z}_n$: the recurrence becomes the third forward difference operator applied to $z_n$ equal to zero, so $z_n$ is a quadratic polynomial. ThusThese three constants give arbitrary initial values $y_0,y_1,y_2$, hence the full third-order solution. If $\mu =0$, the recurrence instead reduces to $y_{n+3}=0$: the first three values are arbitrary and every subsequent value is zero. The nonzero-root formula must not be used to discard those initial values.