Discrete integrating factor
= Discrete integrating factor
{title2=$U_n^{-1}$}
For $x_{n+1}=a_nx_n+b_n$, put $U_0=1$ and $U_n=\prod_{j=1}^na_j$, with $a_j\ne0$. 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 proves
$$
x_{n+1}=U_n\left(x_1+\sum_{j=1}^n\frac{b_j}{U_j}\right).
$$
This is the discrete counterpart of the <integrating factor> for a <first-order linear differential equation>.