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