= Solution
Substitution of $y_n=\lambda^n$ into the <linear recurrence relation> gives $\lambda^n p(\lambda)=0$. Since $\lambda\ne0$, division by $\lambda^n$ proves \b[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>. Thus
$$
\boxed{y_n=(A+Bn+Cn^2)\mu^n,\qquad \mu\ne0.}
$$
These 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$: \b[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.
Back to article page
