A binomial sum problem

Question

I m following the book "Concrete Mathematics" Let $m,\alpha,\beta$ be positive. Please let me know where am I getting wrong in the below calculation?

\begin{align} &\sum_{k}\binom{m+\beta-1}{m+k-1}\binom{m-k}{m-\alpha}(-1)^k\\ &= (-1)^{m-\alpha}\sum_{k}\binom{m+\beta-1}{m+k-1}\binom{k-\alpha-1}{m-\alpha}(-1)^k \quad (\text{by upper negation on page 174})\\ &= (-1)^{m-\alpha}(-1)^{2m+\beta-2}\binom{-m-\alpha}{-\alpha-\beta+1} \quad \text{by 5.24}\\ &=0 \end{align}

But the left hand side is not vanishing.

Answer 1

Your calculation is fine and there's nothing wrong with it. Here we treat this identity slightly different without using the formula (5.24) from Concrete Mathematics by Don Knuth et al.

We use the common definition (5.1) for the binomial coefficients with $r\in\mathbb{C}$ \begin{align*} \binom{r}{k}=\begin{cases} \frac{r(r-1)\cdots(r-k+1)}{k!}\qquad&\text{integer}\ k\geq 0\\ 0\qquad&\text{integer}\ k<0 \end{cases} \end{align*} and we also use the coefficient of operator $[z^k]$ to denote the coefficient of $z^k$ of a series. This way we can write for instance \begin{align*} \binom{r}{k}=[z^k](1+z)^r\tag{1} \end{align*}

We obtain with positive integers $m,\alpha,\beta$: \begin{align*} \color{blue}{\sum_{k\in\mathbb{Z}}}&\color{blue}{\binom{m+\beta-1}{m+k-1}\binom{m-k}{m-\alpha}(-1)^k}\\ &=\sum_{k\geq -m+1}\binom{m+\beta-1}{m+k-1}\binom{m-k}{m-\alpha}(-1)^k\tag{2}\\ &=\sum_{k=0}^{m+\beta-1}\binom{m+\beta-1}{k}\binom{2m-1-k}{m-\alpha}(-1)^{k-m+1}\tag{3}\\ &=\sum_{k=0}^{m+\beta-1}\binom{m+\beta-1}{k}\binom{-m-\alpha+k}{m-\alpha}(-1)^{k+\alpha+1}\tag{4}\\ &=(-1)^{\alpha+1}\sum_{k=0}^{m+\beta-1}\binom{m+\beta-1}{k}[z^{m-\alpha}](1+z)^{-m-\alpha+k}(-1)^k\tag{5}\\ &=(-1)^{\alpha+1}[z^{m-\alpha}](1-z)^{-m-\alpha}\sum_{k=0}^{m+\beta-1}\binom{m+\beta-1}{k}\left(-(1+z)\right)^k\tag{6}\\ &=(-1)^{\alpha+1}[z^{m-\alpha}](1-z)^{-m-\alpha}\left(1-(1+z)\right)^{m+\beta-1}\tag{7}\\ &=(-1)^{\alpha+1}[z^{m-\alpha}](1-z)^{-m-\alpha}(-z)^{m+\beta-1}\\ &=(-1)^{\alpha+\beta+m}[z^{-\alpha-\beta+1}](1-z)^{-m-\alpha}\tag{8}\\ &\,\,\color{blue}{=(-1)^{\alpha+\beta+m}\binom{-m-\alpha}{-\alpha-\beta+1}}\tag{9}\\ &\,\,\color{blue}{=0} \end{align*} and the claim follows.

Comment:

• In (2) we note $\binom{m+\beta-1}{m+k-1}=0$ if the lower index $m+k-1<0$.

• In (3) we shift the index $k$ to start with $k= 0$. We observe that $k$ is restricted due to the upper index of $\binom{m+\beta-1}{m+k-1}$.

• In (4) we use the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (5) we use the coefficient of operator according to (1).

• In (6) we do some rearrangements and use the linearity of the coefficient of operator.

• In (7) we apply the binomial theorem.

• In (8) we apply the rule $[z^{p-q}]A(z)=[z^p]z^qA(z)$.

• In (9) we select the coefficient of $z^{-\alpha-\beta+1}$ and since the lower index $-\alpha-\beta+1<0$ the result $=0$ follows.

Example: $\alpha=2,\beta=6,m=3$; A small plausibility check to see the formula in action.

\begin{align*} \sum_{k}&\binom{m+\beta-1}{m+k-1}\binom{m-k}{m-\alpha}(-1)^k\\ &=\sum_{k}\binom{8}{2+k}\binom{3-k}{1}(-1)^k\\ &=\sum_{k=-2}^6\binom{8}{2+k}(3-k)(-1)^k\\ &=5\binom{8}{0}-4\binom{8}{1}+3\binom{8}{2}-2\binom{8}{3}+1\binom{8}{4}\\ &\qquad-0+(-1)\binom{8}{6}-(-2)\binom{8}{7}+(-3)\binom{8}{8}\\ &=5\cdot 1-4\cdot 8+3\cdot 28-2\cdot 56+1\cdot 70-0+(-1)28-(-2)8+(-3)1\\ &=5-32+84-112+70-0-28+16-3\\ &\,\,\color{blue}{=0}\\ &(-1)^{\alpha+\beta+m}\binom{-m-\alpha}{-\alpha-\beta+1}=(-1)^{11}\binom{-5}{-7}\,\,\color{blue}{=0} \end{align*}