Affine recurrence (source code)

= Affine recurrence
{title2=$x_{n+1}=Ax_n+b$}

An affine recurrence on a finite-dimensional <vector space> has the form $x_{n+1}=Ax_n+b$, where $A$ is a fixed <linear operator> and $b$ a fixed <vector>. Induction gives
$$
x_n=A^nx_0+\sum_{j=0}^{n-1}A^jb.
$$
The sum is empty at $n=0$. If $I-A$ is invertible, the unique <fixed point> is $x_*=(I-A)^{-1}b$, and subtracting it reduces the recurrence to $x_n-x_*=A^n(x_0-x_*)$. The sum formula remains valid when $I-A$ is singular, even when no <fixed point> exists. For example, $A=I$ gives the arithmetic progression $x_n=x_0+nb$. A <stable affine recurrence> additionally has <spectral radius> below one and converges to its <fixed point>.