binomial identity: $\sum_{k=x+y}^{\infty}\binom{k-1}{y-1}\binom{k-y}{x}u^k = \binom{x+y-1}{y-1}\left(\frac{u}{1-u}\right)^{x+y}$?

Question

I met a problem which gave me the left part, and I can compute left part and get right part by Mathematica. However, I don't know how to prove:

$$\sum_{k=x+y}^{\infty}\binom{k-1}{y-1}\binom{k-y}{x}u^k = \binom{x+y-1}{y-1}\left(\frac{u}{1-u}\right)^{x+y}$$ with $x, y \in \mathbb{Z}, x \ge 0, y \ge 1, 0 \le u < 1$.

My Questions:

1. How to prove above binomial identity?

2. Is there simple argument behind it? Since it's quite simple, maybe we can construct two equivalent counting processes.

Answer 1

As explained in this thread, the taylor polynomial of

$$\left(\frac{1}{1-u}\right)^{x+y} = \sum_{k=0}^\infty {k+x+y-1 \choose x+y-1 } u^k$$

So

\begin{align}\binom{x+y-1}{y-1}\left(\frac{u}{1-u}\right)^{x+y} &= \sum_{k=0}^\infty \binom{x+y-1}{y-1}{k+x+y-1 \choose x+y-1 } u^{k+x+y} \\ &= \sum_{k=0}^\infty \frac{(k+x+y-1)!}{x!(y-1)!k!} u^{k+x+y} \\ &= \sum_{k=x+y}^\infty \frac{(k-1)!}{x!(y-1)!(k-x-y)!} u^{k} \\ &= \sum_{k=x+y}^\infty \binom{k-1}{y-1}{k-y \choose x }u^{k} \end{align}

Answer 2

Here is another answer and in the end I can use some help.

Let first term in left hand sum be $s_k$.

Then $s_k = \binom{x + y - 1}{y-1} u^{x+y}$

Then $s_{k+1} = \binom{x + y}{y-1} \binom{x+1}{x} u^{x+y+1}$ After simplification we get

$s_{k+1} = \frac{k}{k+1-x-y} s_k$

And we get

$s_{k+2} = \frac{k+1}{k+2-x-y} s_{k+1} = \frac{(k+1)k}{(k+2-x-y)(k+1-x-y)}$

Let $x+y = n$

So $S = \binom{x + y - 1}{y-1} u^{x+y} \left(1 + \binom{n}{1}u + \binom{n+1}{2}u^2 + ... \right)$

The last term is exactly equal to $\left(\frac{1}{1-u}\right)^n$

After some tinkering I needed to prove:

The $(n-1)th $ derivative of $\frac{u^{n-1}}{(n-1)!(1-u)} = \left(\frac{1}{1-u}\right)^n$

I know this is true but no idea how to prove it. Thanks