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.

A second-order linear recurrence relation normally uses two consecutive initial conditions, but two specified nonconsecutive values may also determine a unique solution of the linear recurrence relation. For two independent homogeneous solutions of the linear recurrence relation $v_n,w_n$, the coefficients in $u_n=u_n^{\mathrm{p}}+A{v}_n+B{w}_n$ are determined by $u_j,u_k$ exactly when $v_j{w}_k-v_k{w}_j\ne 0$. Otherwise the data can be inconsistent or can leave freedom. A nonconsecutive subscript is therefore not by itself evidence of an error.

For a repeated characteristic root of a linear recurrence $r\ne 0$, use $v_n=r^n$, $w_n=n{r}^n$. The determinant is $(k-j)r^{j+k}\ne 0$ for distinct $j,k$, so any such pair of prescribed values determines the two coefficients.

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.

The homogeneous characteristic equation of a linear recurrence isThe repeated characteristic root of a linear recurrence $-1$ supplies the independent terms $(-1{)}^n$ and $n(-1{)}^n$. A constant particular solution is $1/2$, since $1/2=-2(1/2)-1/2+2$. Thus $u_n=1/2+(A+Bn)(-1{)}^n$.

The scan prints $u_2=0$, not $u_1=0$. These initial conditions are consistent. They give $A=1/2$ from $u_0=1$, then $0=1/2+A+2B$, so $B=-1/2$. ThereforeIn particular $u_1=1/2$ and $u_2=0$. Direct substitution verifies the recurrence relation. This is an example of nonconsecutive initial values for a linear recurrence; replacing the printed subscript by 1 would change the answer.