3

I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$. I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask if anyone could take a look at my method so far.

First I set up $A(x) = \sum(a(n)x^n)$ and plugged in the definition of $A(n)$ to get $\sum(A(n-1) + n^2 - n)x^n)$ so that $n^2$ and $n$ could be reduced to their closed forms.

I'm not sure how I should handle the $A(n-1)$ term though without iterating further (perhaps I should?) and I'm starting to wonder if there was a way to produce a generating function for $A(n) - A(n-1)$ so that I could substitute for $n^2 - n$ directly. Does anyone have any suggestions?

Amzoti
  • 56,093
114
  • 511

2 Answers2

3

As you wrote $$ G(x) = \sum_{n=0}^\infty a_n x^n = x + x \sum_{n=1}^\infty a_n x^{n-1} = x + x \sum_{n=1}^\infty \left(a_{n-1} + n(n-1)\right) x^{n-1} = \\ x + x G(x) + x^2 \sum_{n=2}^\infty n(n-1) x^{n-2} = x + x G(x) + x^2 \frac{d^2}{dx^2} \sum_{n=0}^\infty x^{n} $$ Now solve for $G(x)$ and evaluate the remaining sum: $$ G(x) = \frac{x \left(1-x +3 x^2-x^3\right)}{(1-x)^4} $$ Now sure whether this helps finding the closed form for $a_n$.

It is much easier to note that the recurrence reads $a_n - a_{n-1} = n(n-1)$, and thus $$ a_n = n (n-1) + a_{n-1} = n(n-1) + (n-1)(n-2) + a_{n-2} = \sum_{k=1}^{n} k(k-1) + a_0 $$ Thus $$ a_n = 1 + \frac{1}{3} (n-1) n (n+1)$$

Sasha
  • 70,631
  • I see! So the idea is to derive an expression G(x) = x + xG(x) + x^2 etc. so that we can solve for G(x)? Also, to be sure, where did the x out front in the second equality come from? – 114 Mar 30 '13 at 20:34
1

Another take, applying the techniques of Wilf's "generatingfunctionology". First write the recurrence as (no, no sign error there): $$ a_{n + 1} = a_n + n^2 + n \quad a_0 = 1 $$ Define the ordinary generating function: $$ A(z) = \sum_{n \ge 0} a_n z^n $$ By the properties of generating functions, with the operator $D = \dfrac{d}{d z}$ we have: $$ \frac{A(z) - a_0}{z} = A(z) + ((z D)^2 + z D) \frac{1}{1 - z} $$ Substituting $a_0$ gives: $$ A(z) = \frac{1 - 3 z + 5 z^2- z^3}{(1 - z)^4} $$ In partial fractions: $$ A(z) = \frac{2}{(1 - z)^4} - \frac{4}{(1 - z)^3} + \frac{2}{(1 - z)^2} + \frac{1}{1 - z} $$ Expanding by the binomial theorem, with $\binom{-r}{n} = (-1)^n \binom{r + n - 1}{n - 1}$: $$ \begin{align*} a_n &= 2 \binom{n + 3}{3} - 4 \binom{n + 2}{2} + 2 \binom{n + 1}{1} + 1 \\ &= \frac{n^2 - n + 3}{3} \end{align*} $$

vonbrand
  • 27,812