prove $ \sum_{m=0}^{n-k} {n-m-1\choose n-k-m} \\ = [z^{n-k}] (1+z)^{n-1} \sum_{m=0}^{n-k} z^m (1+z)^{-m} $

Question

How it can be show that:

$$ \sum_{m=0}^{n-k} {n-m-1\choose n-k-m} \\ = [z^{n-k}] (1+z)^{n-1} \sum_{m=0}^{n-k} z^m (1+z)^{-m} $$

I tried to use binomial theorem, but since the upper limit does not mach to $n-m-1$ in the binomial coefficient then I could not continue. If you want to prove that please start with the left hand side

Answer 1

Start from right hand side \begin{equation}\begin{aligned} \sum_{m=0}^{n-k}z^m(1+z)^{n-m-1}&=\sum_{m=0}^{n-k}\sum_{\ell=0}^{n-m-1}z^{m+\ell}\begin{pmatrix}n-m-1\\\ell\end{pmatrix}\\ \end{aligned}\end{equation} So we see the coefficient of $z^{n-k}$ is at $\ell=n-k-m$, and the result follows.

Answer 2

Let $n=p+k$, multiply by $z^p$, and sum to compute the generating function: $$ \begin{align} \sum_{p=0}^\infty\sum_{m=0}^p\binom{p+k-1-m}{p-m}z^p &=\sum_{m=0}^\infty\sum_{p=m}^\infty\binom{p+k-1-m}{p-m}z^p\tag1\\ &=\sum_{m=0}^\infty\sum_{p=m}^\infty(-1)^{p-m}\binom{-k}{p-m}z^p\tag2\\ &=\sum_{m=0}^\infty z^m\sum_{p=0}^\infty(-1)^p\binom{-k}pz^p\tag3\\ &=\sum_{m=0}^\infty\frac{z^m}{(1-z)^k}\tag4\\ &=\frac1{(1-z)^{k+1}}\tag5 \end{align} $$ Explanation:
$(1)$: change order of summation
$(2)$: apply negative binomial coefficients
$(3)$: substitute $p\mapsto p+m$
$(4)$: sum in $p$
$(5)$: sum in $m$

Now use the generating function $$ \begin{align} \sum_{m=0}^{n-k}\binom{n-1-m}{n-k-m} &=\left[z^{n-k}\right]\frac1{(1-z)^{k+1}}\tag6\\ &=(-1)^{n-k}\binom{-k-1}{n-k}\tag7\\ &=\binom{n}{n-k}\tag8\\[6pt] &=\left[z^{n-k}\right](1+z)^n\tag9\\[6pt] &=\left[z^{n-k}\right](1+z)^{n-1}\frac1{1-\frac{z}{1+z}}\tag{10}\\ &=\left[z^{n-k}\right](1+z)^{n-1}\sum_{m=0}^\infty\frac{z^m}{(1+z)^m}\tag{11}\\ &=\left[z^{n-k}\right](1+z)^{n-1}\sum_{m=0}^{n-k}\frac{z^m}{(1+z)^m}\tag{12} \end{align} $$ Explanation:
$\phantom{1}(6)$: apply $(5)$; i.e. pull out the $p=n-k$ coefficient
$\phantom{1}(7)$: apply the Binomial Theorem
$\phantom{1}(8)$: apply negative binomial coefficients
$\phantom{1}(9)$: apply the Binomial Theorem
$(10)$: $1+z=\left(1-\frac{z}{1+z}\right)^{-1}$
$(11)$: apply the power series for $(1-x)^{-1}$
$(12)$: discard terms with powers of $z$ higher than $n-k$

Answer 3

What I intended to do at the linked post was this:

$$\sum_{m=0}^{n-k} {n-m-1\choose n-k-m} \\ = \sum_{m=0}^{n-k} [z^{n-k-m}] (1+z)^{n-m-1} \\ = \sum_{m=0}^{n-k} [z^{n-k}] z^m (1+z)^{n-m-1} \\ = [z^{n-k}] \sum_{m=0}^{n-k} z^m (1+z)^{n-m-1} \\ = [z^{n-k}] (1+z)^{n-1} \sum_{m=0}^{n-k} z^m (1+z)^{-m}.$$

When $f(z) = \cdots + z^{n-k-m} f_{n-k-m} + \cdots$ then $z^m f(z) = \cdots + z^{n-k} f_{n-k-m} + \cdots$ and therefore $f_{n-k-m} = [z^{n-k-m}] f(z) = [z^{n-k}] z^m f(z).$