I'm currently reading through a proof (by Galvin) finding the generating function for the Delannoy numbers and I'm currently stuck at one step. I've been staring at this for a while, and feel that I'm just missing something.
To be clear we're going from $(0,0)$ to $(n,m)$. I'm at the point where we have \begin{align*} d_{n,m}=\sum_{k\geq 0} \binom{n}{k}\binom{n+m-k}{n}. \end{align*} I'm stuck at the next part.
" It follows that $d_{n,m}$ is the coefficient of $y^m$ in $\sum_{k\geq 0}\binom{n}{k}\frac{y^k}{(1-y)^{n+1}}$. Now the coefficient of $y^m$ in $\frac{y^k}{(1-y)^{n+1}}$ is the same as the coefficient of $y^{m-k}$ in $\frac{1}{(1-y)^{n+1}}$, which is $\binom{n+m-k}{n}\dots $"
Why is the coefficient for the last part $\binom{n+m-k}{n}$? It's presented in a way where it seems obvious, but I'm just not seeing it at the moment. Any help would be greatly appreciated.
We have \begin{eqnarray*} d_{n,m}= \sum_{k=0}^{\color{red}{m}} \binom{n}{k} \binom{n+m-k}{n}. \end{eqnarray*} Now multiply by $y^m$ and sum on $m$ gives \begin{eqnarray*} \phi_n(y) = \sum_{m=0}^{\infty} d_{n,m} y^m &=& \sum_{m=0}^{\infty} \sum_{k=0}^{m} \binom{n}{k} \binom{n+m-k}{n} y^m \\ &=& \sum_{k=0}^{\infty} \binom{n}{k} \sum_{m=k}^{\infty} \binom{n+m-k}{n} y^m \\ &=& \sum_{k=0}^{\infty} \binom{n}{k} \frac{ y^k}{(1-y)^{n+1}}. \\ \end{eqnarray*}