Are recursive geometric sequence with second term solvable?

Question

Consider the following recursive formula:

$$ U_n = a U_{n-1}+f(n) $$

For $f(n)=b$ ($f$ independent on $n$), it is possible to find the analytic expression for $U_n$. My question is: Are there analytic expression of $U_n$ for an arbitrary $f(n)$ ?

Answer 1

Suppose we have the recurrence $$f_{n}=a_n+b_nf_{n-1}\qquad n\ge1,\ \ f_0\text{ given}.$$ Set $B_n=\prod_{k=1}^{n}b_k$, and divide through by $B_n$. We get $$\frac{f_n}{B_n}=\frac{a_n}{B_n}+\frac{f_{n-1}}{B_{n-1}}.$$ Setting $F_n=f_n/B_n$ and $A_n=a_n/B_n$, $$F_m-F_{m-1}=A_m.$$ Sum both sides from $m=1$ to $n$: $$F_n-F_0=\sum_{m=1}^{n}A_m,$$ which is $$f_n=f_0B_n+\sum_{m=1}^{n}a_m\frac{B_n}{B_m}$$ which can be simplified more if desired.