# On the calculus of recurrence relations using generating functions?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory:

I don't understand what he's doing in the summations , I see that he mixed the general recurrence inside a generating function. But for example, the general recurrence is:

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$

And here it's:

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad$

Which is different from the general recurrence. I guess they jumped too many steps in here, I can't follow it.

• He is simply saying that $a_k x^k = (b a_{k-1} +c) x^k$. Feb 17, 2015 at 3:40

I’ll take it a line at a time.

$$G(x)=\sum_{k\ge 0}a_kx^k$$

This is just the definition of the generating function for the sequence $\langle a_k:k\in\Bbb N\rangle$.

$$\sum_{k\ge 0}a_kx^k=a_0+\sum_{k\ge 1}(ba_{k-1}x^k+cx^k)$$

This combines three baby steps into one longer step:

\begin{align*} \sum_{k\ge 0}a_kx^k&=a_0+\sum_{k\ge 1}a_kx^k\\ &=a_0+\sum_{k\ge 1}(ba_{k-1}+c)x^k\\ &=a_0+\sum_{k\ge 1}(ba_{k-1}x^k+cx^k) \end{align*}

First we break off the $k=0$ term, then we use the fact that $a_k=ba_{k-1}+c$, and then we multiply out inside the summation.

$$a_0+\sum_{k\ge 1}(ba_{k-1}x^k+cx^k)=a_0+bx\sum_{k\ge 0}a_kx^k+cx\sum_{k\ge 0}x^k$$

Here again several small steps have been combined. The first two split the summation into two summations and pull out common factors in each:

\begin{align*} a_0+\sum_{k\ge 1}(ba_{k-1}+cx^k)&=a_0+\sum_{k\ge 1}ba_{k-1}x^k+\sum_{k\ge 1}cx^k\\ &=a_0+bx\sum_{k\ge 1}a_{k-1}x^{k-1}+cx\sum_{k\ge 1}x^{k-1} \end{align*}

Now let $\ell=k-1$, and note that $k\ge 1$ if and only if $\ell\ge 0$. THus, we can rewrite that last expression as

$$a_0+bx\sum_{\ell\ge 0}a_\ell x^\ell+cx\sum_{\ell\ge 0}x^\ell\;.$$

There’s no real reason to clutter things up with the extra index name $\ell$, though: we might just as well rename $\ell$ to $k$ and write this as

$$a_0+bx\sum_{k\ge 0}a_k x^k+cx\sum_{k\ge 0}x^k\;.$$

We’ve simply shifted the indexing by one place.

• I guess this part is not clear: $$a_0+\sum_{k\ge 1}(ba_{k-1}x^k+cx^k)=a_0+bx\sum_{k\ge 0}a_kx^k+cx\sum_{k\ge 0}x^k$$ Do we push the $bx,cx$ outside the summation because they have already been processed by $\sum_{k\geq 1}$? I guess this make sense because the next summations start from $k\geq 0$. Feb 17, 2015 at 22:19
• @Vÿska: No, it’s just the distributive law. $\sum_kcx^k=c\sum_kx^k$ is no different from $ca+cb=c(a+b)$. Feb 17, 2015 at 22:22
• Oh, I got it. I was being stupid of not checking it by expanding a few terms. I did it now and I noticed they are the same. $$a_0+\sum_{k\ge 1}(ba_{k-1}x^k+cx^k)=a_0+(ba_0x^1+cx^1+\cdots)+(ba_1x^2+cx^2+\dots)$$ $$a_0+bx\sum_{k\ge 0}a_kx^k+cx\sum_{k\ge 0}x^k=a_0+(ba_0x^1+ba_1x^2+\dots)+(cx^1+cx^2+ \dots )$$ Feb 17, 2015 at 22:31