# Inhomogenous recurrence relations

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)$ )

## 2 Answers

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 .

In addition to Wilf I also recommend Graham, Knuth, and Patashnik's Concrete Mathematics for these kinds of questions. GKP has a lot of good material on, for example, techniques for estimating the growth rate of recurrences even when closed forms seem difficult to obtain.

• Recommendation seconded! – Robin Chapman Apr 13 '10 at 18:39
• Thirded. (Too bad isn't GKP isn't available online.) – Michael Lugo Apr 13 '10 at 23:12