Variable-coefficient affine recurrence ($x_{n+1}=a_n{x}_n+b_n$)

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.