Linear recurrence relation

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.

For $b\ne 1$, subtract the equilibrium $u_{\ast }=a/(1-b)$ to get $u_{k+1}-u_{\ast }=b(u_k-u_{\ast })$. Hence $u_k=u_{\ast }+b^k(u_0-u_{\ast })$. For $b=1$, the solution is $u_k=u_0+ka$. The exceptional factor $0^0$ in a formula with $b=0,k=0$ is avoided by retaining the given initial value.

A linear recurrence matrix advances a vector of quantities by a fixed linear map: $v_{n+1}=M{v}_n$, hence $v_n=M^n{v}_0$. It can encode several simultaneous linear recurrences and need not satisfy the normalization required of a Markov chain transition matrix.

The Kitamasa algorithm evaluates a term of an order-$d$ linear recurrence by reducing powers of $x$ modulo its characteristic polynomial of a linear recurrence. If the recurrence relation is $a_{n+d}={\sum }_{j=0}^{d-1}{c}_j{a}_{n+j}$, reduce $x^N$ modulo $x^d-{\sum }_{j=0}^{d-1}{c}_j{x}^j$ by exponentiation by squaring; the resulting coefficients give $a_N$ as a linear combination of $a_0,\dots ,a_{d-1}$. Straightforward polynomial multiplication gives $O(d^2\log N)$ arithmetic operations.

For two solutions of the linear recurrence relation $x_{n+2}+b_n{x}_{n+1}+c_n{x}_n=0$, their discrete Wronskian obeys $W_{n+1}=c_n{W}_n$. Substitute the recurrence into $p_{n+1}{q}_{n+2}-p_{n+2}{q}_{n+1}$: the $b_n$ terms cancel and the remaining expression is $c_n(p_n{q}_{n+1}-p_{n+1}{q}_n)$. Iteration gives $W_{n+1}=W_1{\prod }_{m=1}^n{c}_m$, including when some $c_m$ vanish. A nonzero discrete Wronskian proves linear independence of the two solutions.

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.

A variable-coefficient affine recurrence is a linear recurrence relation with coefficients allowed to depend on the index. If every $a_n$ is nonzero, a discrete integrating factor reduces it to a telescoping series.

For $x_{n+1}=a_n{x}_n+b_n$, put $U_0=1$ and $U_n={\prod }_{j=1}^n{a}_j$, with $a_j\ne 0$. Dividing by this accumulated homogeneous growth gives $z_n=x_n/U_{n-1}$ and $z_{n+1}-z_n=b_n/U_n$. A telescoping series then provesThis is the discrete counterpart of the integrating factor for a first-order linear differential equation.

For a constant-coefficient linear recurrence relation, substituting a trial sequence $u_n=r^n$ produces a polynomial equation in $r$ called its characteristic equation. Repeated roots contribute factors polynomial in $n$.

A nonzero root $\mu$ of multiplicity $m$ supplies $m$ independent solutions $n^j{\mu }^n$ to a constant-coefficient linear recurrence relation. Substitution $y_n={\mu }^n{z}_n$ reduces its repeated factor to the $m$th forward difference operator. A zero root needs separate initial-data treatment: for characteristic polynomial ${\lambda }^m$, the recurrence is $y_{n+m}=0$, leaving the first $m$ values arbitrary.

For a linear recurrence relation with two distinct characteristic equation of a linear recurrence roots $r_1,r_2$, the solution is $u_n=A{r}_1^n+B{r}_2^n$. If $|r_1|<1<|r_2|$, boundedness for $n\to \infty$ forces $B=0$, and $u_0$ fixes $A$. This selects the decaying discrete mode in a finite difference method for a boundary problem on an unbounded interval. Roots on the unit circle require separate treatment; a repeated root there can contribute an unbounded factor $n$.

For a sequence $(u_n)$, the ordinary generating function isMultiplying a linear recurrence by $x^n$ and summing converts shifts of the sequence into polynomial multiples of $G$.

The sequence $\lfloor n/2\rfloor$ has generating function

An affine recurrence has the form $x_{n+1}=A{x}_n+b$ and is solved by a matrix geometric sum.

If the spectral radius of $A$ is below one, $x_{n+1}=A{x}_n+b$ converges to the unique fixed point $(I-A{)}^{-1}b$.