2
$\begingroup$

The Full Question

Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$

My Research

Scanned the website for similar answers, reviewed the following links:

Solve the following recurrences using generating functions.

can we use generating functions to solve the recurrence relation $a_n = a_{n-1} + a_{n-2}$, $a_1=1$, $a_2=2$?

Solving a recurrence equation using generating functions

Using Generating Functions to Solve Recursions

Solve the following recursive relation by using generating functions

Solve a recursion using generating functions?

Solving recurrences using generating functions

None of them would make my question a duplicate and none of them really addressed what I was having difficulty with.

My Work

If we multiply each side by $x^{n+1}$ and sum each of the possible cases $a_0,a_1,\dots$ we have:

$$\sum\limits_{j=0}^{\infty}{a_{n+1}x^{n+1}} - x\sum\limits_{j=0}^{\infty}a_nx^n = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$

If we let $f(x) = \sum\limits_{j=0}^{\infty}a_nx^n$ our equation transforms into:

$$f(x)-a_0 -xf(x) = \sum\limits_{j=0}^{\infty}n^2x^{n+1}$$

Factoring $f(x)$ and observing the LHS is a well known generating functions and using the fact that $a_0 = 1$, we get:

$$f(x)(1-x) = \frac{x(1+x)}{(1-x)^3} + 1 \implies f(x) = \frac{x(1+x)}{(1-x)^4} + \frac{1}{1-x}$$

We now need the coefficients of $x^n$ of these two functions we are adding. The right function it is well known that is has coefficients of $1$. We need partial fraction decomposition to obtain the coefficients of the left hand side.

$$\frac{x(1+x)}{(1-x)^4}= \frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+\frac{D}{(1-x)^4}$$

$\implies x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$

Expanding this, we have

$Ax^3+3Ax^2 - 3Ax + A + Bx^2 -2Bx + B +C -Cx +D$

Which gives us the system of equations:

1) $A+B+C+D = 0$

2) $-3A-2B-C =1$

3) $3A+B = 1$

4) $A = 0$

5) $D = 0$

$3(0)+B=1 \implies B=1$ Using equations 3&4

$-3(0) -2 - C=1\implies C=3$ Using equations Using equations 2&1 and the result above

$0+1+3+0 = 0$ plugging in our results to equation 1

that is obviously not correct. Where did I make my mistake. I feel I'm very close and must have messed up the partial fraction decomposition somewhere, but maybe the mistake is somewhere else. Can anyone find where I went wrong?

$\endgroup$
5
  • $\begingroup$ How do you conclude that $D=0$? $\endgroup$
    – Chappers
    Mar 8, 2015 at 23:24
  • $\begingroup$ Here are the correct values of $A,B,C,D$: $A = 0$, $B =1$, $C = -3$, and $D=2$. $\endgroup$
    – Braindead
    Mar 8, 2015 at 23:26
  • $\begingroup$ @Chappers I compared coefficients with LHS. There is no constant term on the LHS. $\endgroup$
    – Dunka
    Mar 8, 2015 at 23:26
  • $\begingroup$ @Dunka Looking at the constant terms is what got equation 1), right? You can't conclude that $D=0$ from that though. $\endgroup$
    – Braindead
    Mar 8, 2015 at 23:28
  • $\begingroup$ @Braindead I think I see where I made the mistake now. D does not equal 0. Got a bit ahead of myself. $\endgroup$
    – Dunka
    Mar 8, 2015 at 23:29

2 Answers 2

3
$\begingroup$

You made a mistake in solving $$ x(1+x)= A(1-x)^3+B(1-x)^2+C(1-x)+D$$

A faster way to solve this is the following: $$x = 1 \Rightarrow D=2$$

Next derivate $$1+2x=-3A(1-x)^2-2B(1-x)-C$$ plug in $x=1$. Then derivate again, and plug in $x=1$. Continue...

$\endgroup$
0
$\begingroup$

Define the generating function $A(z) = \sum_{n \ge 0} a_n z^n$. Take the recurrence, multiply by $z^n$, sum over $n \ge 0$:

$$ \sum_{n \ge 0} a_{n + 1} z^n - \sum_{n \ge 0} a_n z^n = \sum_{n \ge 0} n^2 z^n $$

Recognize some sums, note that:

$\begin{align} \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - z} \\ &= \frac{z}{(1 - z)^2} \\ \sum_{n \ge 0} n^2 z^n &= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{z}{(1 - z)^2} \\ &= \frac{z + z^2}{(1 - z)^3} \\ \end{align}$

$$ \frac{A(z) - a_0}{z} - A(z) = \frac{z + z^2}{(1 - z)^3} $$

Plug in $a_0 = 1$, solve for $A(z)$, split into partial fractions:

$\begin{align} A(z) &= \frac{1 - 3 z + 4 z^2}{1 - 4 z + 6 z^2 - 4 z^3 + z^4} \\ &= \frac{4}{(1 - z)^2} + \frac{5}{(1 - z)^3} + \frac{2}{(1 - z)^4} \end{align}$

Consider that:

$$ (1 - z)^{-r} = \sum_{n \ge 0} (-1)^n \binom{-r}{n} z^n = \sum_{n \ge 0} \binom{r + n - 1}{r - 1} z^n $$

Note that $\binom{n + r - 1}{r - 1}$ is a polynomial of degree $r - 1$ in $n$.

Pick the coefficient of $z^n$ of $A(z)$:

$\begin{align} a_n &= 4 \binom{n + 1}{1} + 5 \binom{n + 2}{2} + 2 \binom{n + 3}{3} \\ &= \frac{2 n^3 + 27 n^2 + 91 n + 66}{6} \end{align}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.