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

  • 1
    $\begingroup$ Try including any ideas you might have or anything you know about the specific subject in the post. $\endgroup$ – 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


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\;,$$


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

| cite | improve this answer | |

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.

| cite | improve this answer | |

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.