Linear recurrence relation

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$.

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$.