Solutions of recursive equations using generating functions

Question

Can someone explain me how solve exercise like this?

Find solutions of recursive equations using generating functions:

$$ a_n = a_{n-1} + 2n - 1\\ a_0= 0\\ n\ge 1 $$

Answer 1

I start with the recurrence $a_n=a_{n-1}+2n-1$ and ask first whether it works at $n=0$ if we assume that $a_k=0$ for all $k<0$. In this case it does not:

$$a_{-1}+2\cdot0-1=0+0-1=-1\ne a_0\;.$$

I correct it by adding a term $[n=0]$, where the square brackets are Iverson brackets, to make

$$a_n=a_{n-1}+2n-1+[n=0]\;.$$

Now multiply through by $x^n$ and sum over $n$:

$$\begin{align*} \sum_{n\ge 0}a_nx^n&=\sum_{n\ge 0}a_{n-1}x^n+2\sum_{n\ge 0}nx^n-\sum_{n\ge 0}x^n+\sum_{n\ge 0}[n=0]x^n\\ &=x\sum_{n\ge 0}a_{n-1}x^{n-1}+2\sum_{n\ge 0}nx^n-\sum_{n\ge 0}x^n+1\\ &=x\sum_{n\ge 0}a_nx^n+2\sum_{n\ge 0}nx^n-\frac1{1-x}+1 \end{align*}$$

Now $\sum_{n\ge 0}a_nx^n$ is the generating function; if we call it $A(x)$, we now have

$$A(x)=xA(x)+2\sum_{n\ge 0}nx^n-\frac1{1-x}+1\;,$$

so

$$(1-x)A(x)=2\sum_{n\ge 0}nx^n-\frac{x}{1-x}\;,$$

and hence

$$A(x)=\frac2{1-x}\sum_{n\ge 0}nx^n-\frac{x}{(1-x)^2}\;.\tag{1}$$

To finish the job you’ll need to find a closed form for $\sum_{n\ge 0}nx^n$. Note that $nx^n=x\frac{d}{dx}(x^n)$, so

$$\sum_{n\ge 0}nx^n=x\sum_{n\ge 0}nx^{n-1}=x\frac{d}{dx}\left(\sum_{n\ge 0}x^n\right)=x\frac{d}{dx}\left(\frac1{1-x}\right)=\frac{x}{(1-x)^2}\;,$$

and now it’s just a matter of substituting this into $(1)$ and simplifying.

Answer 2

Define a generating function $A(z) = \sum_{n \ge 0} a_n z^n$, for simplicity shift the recurrence to get rid of subtractions in indices:

$\begin{align*} a_{n + 1} &= a_n + 2 n +1 \end{align*}$

Multiply by $z^n$, sum over $n \ge 0$, recognize resulting sums:

$\begin{align*} \sum_{n \ge 0} a_{n + 1} z^n &= \frac{A(z) - a_0}{z} \\ \sum_{n \ge 0} z^n &= \frac{1}{1 - z} \\ \sum_{n \ge 0} n z^n &= z \frac{d}{d z}\sum_{n \ge 0} z^n \end{align*}$

This gives an equation for $A(z)$. Solve that one, express as partial fractions (a computer algebra system is of much help here), and figure out the coefficient of $z^n$ in the resulting terms.