The logic behind rearranging summations - generating functions 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)
 A: 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$.
A: 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}$.
