# Solutions of recursive equations using generating functions

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$$

• Try including any ideas you might have or anything you know about the specific subject in the post. – Micah Windsor May 15 at 0:30

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.

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.