1
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
6
$\begingroup$

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 .

Improve this answer
$\endgroup$
6
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Recommendation seconded! $\endgroup$
    – Robin Chapman
    Commented Apr 13, 2010 at 18:39
  • $\begingroup$ Thirded. (Too bad isn't GKP isn't available online.) $\endgroup$
    – Michael Lugo
    Commented Apr 13, 2010 at 23:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .