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 \)?

No comments:

Post a Comment