Would someone be able to point me to a good resource explaining step by step the process for solving inhomogenous recurrence relations? (ie something of the form $ a\_n = \sum{{b\_i}{a\_{n-i}}} + f(n)$ )



Inhomogenous recurrence relations
One standard method is generating functions. Set $A(t)=\sum\_{n=0}^\infty a\_n t^n$
and $B(t)=\sum\_{i=1}^\infty b\_i t^i$. Then
$$A(t)=a\_0+B(t)A(t)+\sum\_n f(n)t^n$$
so that
$$A(t)=(1-B(t))^{-1}\left(a\_0+\sum\_n f(n)t^n\right).$$
For an excellent text on generating functions, see Herb Wilf's
*generatingfunctionology*:
<http://www.math.upenn.edu/~wilf/DownldGF.html> .


