A sum including binomial coefficients I would like to prove the following equality:
$$\sum_k (-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}=\sum_{k=0}^{n-2}\binom{2n-k-2}{n-1}\binom{n-2}{k}$$
but the power over two and the switch on the number of sums bothers me. 
Any help would be welcome.
(the equality it part of Note 1.41 in the book "Analytic Combinatorics")
 A: The following answer is purely algebraic. We transform both sides of OPs expression to finally obtain the same representation. We also use the coefficient of operator $[z^n]$ to denote the coefficient $a_n$ of $z^n$ of a series $\sum_{k=0}^{\infty}a_kz^k$. 

At first we transform the right-hand side. It's the easier one.
\begin{align*}
\sum_{k=0}^{n-2}&\binom{2n-k-2}{n-1}\binom{n-2}{k}\\
&=\sum_{k=0}^{n-2}\binom{n+k}{n-1}\binom{n-2}{k}\tag{1}\\
&=\sum_{k=0}^{n-2}[z^{n-1}](1+z)^{n+k}\binom{n-2}{k}\tag{2}\\
&=[z^{n-1}](1+z)^n\sum_{k=0}^{n-2}\binom{n-2}{k}(1+z)^{k}\\
&=[z^{n-1}](1+z)^n(2+z)^{n-2}\tag{3}\\
&=\sum_{k=0}^{n-1}\left([z^k](1+z)^n\right)\left([z^{n-1-k}](2+z)^{n-2}\right)\\
&=\sum_{k=0}^{n-1}\binom{n}{k}\binom{n-2}{n-1-k}2^{(n-2)-(n-1-k)}\\
&=\sum_{k=1}^{n-1}\binom{n}{k}\binom{n-2}{k-1}2^{k-1}\tag{4}\\
\end{align*}

Comment:


*

*In (1) we change the order of summation by transforming the index $k$ with $n-2-k$

*In (2) we represent the binomial coefficient $\binom{n+k}{n-1}$ as the coefficient of $z^{n-1}$ of $(1+z)^{n+k}$

*In (3) we write the sum as polynomial $(2+z)^{n-2}$. 

And here's the left-hand side. 
\begin{align*}
 \sum_{k=0}^{n-1}&(-1)^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{k}\\
 &=(-1)^{n-1} \sum_{k=0}^{n-1}(-2)^k\binom{n}{k+1}\binom{n+k-1}{n-1}\\
&=(-1)^{n-1} \sum_{k=1}^{n}(-2)^{k-1}\binom{n}{k}\binom{n+k-2}{n-1}\\
&=\frac{1}{2}(-1)^{n-1} \sum_{k=1}^{n}(-2)^{k}\binom{n}{k}[z^{n-1}](1+z)^{n+k-2}\\
&=\frac{1}{2}(-1)^{n-1} [z^{n-1}](1+z)^{n-2}\sum_{k=1}^{n}\binom{n}{k}(-2)^k(1+z)^{k}\\
&=\frac{1}{2}(-1)^{n-1} [z^{n-1}](1+z)^{n-2}\left\{(-1-2z)^n-1\right\}\\
&=\frac{1}{2} [z^{n-1}](1+z)^{n-2}\left\{(1+2z)^n+1\right\}\tag{5}\\
&=\frac{1}{2} [z^{n-1}](1+z)^{n-2}(1+2z)^n\\
&=\frac{1}{2}\sum_{k=0}^{n-1}\left([z^k](1+2z)^n\right)\left([z^{n-1-k}](1+z)^{n-2}\right)\\
&=\frac{1}{2}\sum_{k=0}^{n-1}\binom{n}{k}2^k\binom{n-2}{k-1}\tag{6}\\
\end{align*}
Since the expressions (4) and (6) are equal, the claim follows.
The summand with $k=0$ does not contribute anything. So we can start with $k=1$ and after an index transformation we obtain the somewhat more convenient representation
  \begin{align*}
\sum_{k=0}^{n-2}\binom{n}{k+1}\binom{n-2}{k}2^k
\end{align*}

Comment:


*

*In (5) we need not to consider the summand  $+1$ in the rightmost expression. It does not contribute anything to the coefficient $[z^{n-1}]$.

