## Tuesday, March 26, 2013

### Solving Recurrences with Difference Equations

Here's an example from Robert Sedgewick's course on analytic combinatorics.

Solve the recurrence $a_n = 3 a_{n−1} − 3 a_{n−2} + a_{n−3}$ for $$n>2$$ with $$a_0=a_1=0$$ and $$a_2=1$$.

Let $$f(n) = a_n$$; in the language of difference equations the above becomes simply
$\frac{{\Delta^3} f}{{\Delta n}^3 } = 0 .$ Immediately,
$f(n) = c_2 n^2 + c_1 n + c_0 .$ Applying the initial conditions we get
$c_0 = 0, c_2 + c_1 = 0, 4 c_2 + 2 c_1 = 1,$ and so the solution is $$a_n = \frac{1}{2} n^2 - \frac{1}{2} n$$.

Now what if the initial conditions are changed so $$a_1 = 1$$?