The logic behind rearranging summations - generating functions

Question

I'm learning about generating functions, and one part that I am struggling with is the logic behind rearranging summations (particularly double summations).

I'll illustrate an example:

Using the Lagrangean Inversion theorem, I get that the $z^n$ coefficient is given by: $$S_n=\frac{1}{n}[u^{n-1}]\left(\frac{1-u}{1-2u}\right)^n$$ Expanding this out I get:

$$S_n=\frac{1}{n}[u^{n-1}]\sum^{n}_{k=0}\binom{n}{k}(-1)^ku^k * \sum^{\infty}_{j=0}\binom{j+n-1}{j}(2u)^j$$ Which I have brought together as: $$\frac{1}{n}[u^{n-1}]\sum^{n}_{k=0}\sum^{\infty}_{j=0}\binom{n}{k}\binom{j+n-1}{j}2^j(-1)^ku^{j+k}$$ Where I'm using the fact that (taken from my course notes): $$\frac{1}{(1-x)^{p+1}}=\sum_q\binom{q+p}{q}$$ I know the answer is:

$$S_n=\frac{(-1)^{n-1}}{n}\sum_k(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}$$

My Problem

I can't work out the reasoning that allows you to bring the double summation together in the type of situation. I'm fairly sure I need to apply the restriction $j+k=n-1$, since that is the coefficient we are interested in, but I don't know where to go.

(For reference, this is I.41 on pg70 of Analytic Combinatorics by Flajolet and Sedgewick, available as a free download via a simple Google search)

Answer 1

You need to show that

$$\frac{1}{n}[u^{n-1}]\sum^{n}_{k=0}\sum^{\infty}_{j=0}\binom{n}{k}\binom{j+n-1}{j}2^j(-1)^ku^{j+k}=\frac{(-1)^{n-1}}{n}\sum_k(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}\;.$$

The only terms that need to be considered on the lefthand side are those for which $j+k=n-1$, so we can let $j$ run from $0$ to $n-1$ and take $k=n-1-j$ to reduce the lefthand side to

$$\frac1n\sum_{j=0}^{n-1}\binom{n}{n-1-j}\binom{j+n-1}j2^j(-1)^{n-1-j}\;.$$

Now rename $j$ to $k$:

$$\frac1n\sum_{k=0}^{n-1}\binom{n}{n-1-k}\binom{k+n-1}k2^k(-1)^{n-1-k}\;.$$

Finally,

$$\binom{n}{n-1-k}=\binom{n}{n-(n-1-k)}=\binom{n}{k+1}\;,$$

and $2^k(-1)^{n-1-k}=2^k(-1)^{n-1+k}=(-2)^k(-1)^{n-1}$, so

$$\frac1n\sum_{k=0}^{n-1}\binom{n}{n-1-k}\binom{k+n-1}k2^k(-1)^{n-1-k}=\frac{(-1)^{n-1}}n\sum_{k=0}^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}k\;,$$

as desired.

Added: If instead we let $k$ run from $0$ to $n-1$ and take $j=n-1-k$, the lefthand side becomes

$$\frac1n\sum_{k=0}^{n-1}\binom{n}k\binom{(n-1-k)+n-1}{n-1-k}2^{n-1-k}(-1)^k\;.$$

Letting $\ell=n-1-k$ and noting that

$$\binom{n}k=\binom{n}{n-k}=\binom{n}{\ell+1}\;,$$

we can rewrite this as

$$\begin{align*} \frac1n\sum_{\ell=0}^{n-1}\binom{n}{\ell+1}\binom{\ell+n-1}{\ell}2^\ell(-1)^{n-1-\ell}&=\frac1n\sum_{\ell=0}^{n-1}\binom{n}{\ell+1}\binom{\ell+n-1}{\ell}2^\ell(-1)^{n-1+\ell}\\\\ &=\frac{(-1)^{n-1}}n\sum_{\ell=0}^{n-1}(-2)^\ell\binom{n}{\ell+1}\binom{n+\ell-1}\ell\;, \end{align*}$$

exactly as before except that the index variable is $\ell$ instead of $k$.

Answer 2

Here is a slightly different derivation.

We obtain \begin{align*} \frac{1}{n}&[u^{n-1}]\sum_{k=0}^n\sum_{j=0}^\infty\binom{n}{k}\binom{j+n-1}{j}2^j(-1)^ku^{j+k}\\ &=\frac{1}{n}\sum_{k=0}^{n-1}[u^{n-1-k}]\sum_{j=0}^\infty\binom{n}{k}\binom{j+n-1}{j}2^j(-1)^ku^{j}\tag{1}\\ &=\frac{1}{n}\sum_{k=0}^{n-1}[u^{k}]\sum_{j=0}^\infty\binom{n}{k+1}\binom{j+n-1}{j}2^j(-1)^{n-k-1}u^{j}\tag{2}\\ &=\frac{(-1)^{n-1}}{n}\sum_{k=0}^{n-1}\binom{n}{k+1}\binom{k+n-1}{k}(-2)^k\tag{3} \end{align*}

Comment:

• In (1) we apply the rule $[u^p]u^qA(u)=[u^{p-q}]A(u)$ with $p=n-1$ and $q=k$. We also set the upper limit of the outer sum to $n-1$ since the exponent of $u^{n-1-k}$ is non-negative.

• In (2) we change the order of summation $k\rightarrow n-1-k$ and apply the rule $\binom{p}{q}=\binom{p}{p-q}$.

• In (3) we select the coefficient of $u^k$ and factor out $(-1)^{n-1}$.