My question may be really elementary, simple, or obvious, and yet the solution misses me.

My question is on a combinatorics answer to the question Proving $\sum\limits_{m=0}^M \binom{m+k}{k} = \binom{k+M+1}{k+1}$.

I follow most of the mathematics in the answer, such as the Chu-Vandermonde identity, identity $(\mathbf{1})$ below,


and all the steps except for two, namely, how does $(\mathbf{6})$ follow from $(\mathbf{5})$?

$$ \begin{align} &=(-1)^{M-n}\binom{-k-n-2}{M-n}\tag{5}\\ &=\binom{M+k+1}{M-n}\tag{6}\\ \end{align}$$

The following shows my attempt to answer that question.

I noticed that $(\mathbf{5})$ takes the same form as the $(-1)^k\binom{n+k-1}{k}$ of identity $(\mathbf{1})$. For example, both have $(-1)$ raised to a power $k$, and multiplied by a binomial coefficient that is indexed by $k$. Now, if the expression $$(-1)^{M-n}\binom{-k-n-2}{M-n}\tag{5}$$

is somehow in a form compatible with identity $(\mathbf{1})$, then we can substitute $(\mathbf{5})$ into the RHS of $(\mathbf{1})$, and the LHS result of $(\mathbf{1})$ will hopefully equal $(\mathbf{6})$.

Still, it's not immediately obvious to me if or how $(\mathbf{5})$ can be transformed into the RHS of $(\mathbf{1})$, so that we can apply the identity $(\mathbf{1})$ to show $(\mathbf{5}) = (\mathbf{6}) $ .

What algebraic manipulations, renaming, substitutions, identities or otherwise, are needed to show $(\mathbf{5}) = (\mathbf{6})$?

  • $\begingroup$ You can cheat a little, by realizing that $(-1)^{M-n}$ can only ever equal $-1$ or $1$. It could be easier to handle both cases separately, and then show they give the same result. $\endgroup$ – Newb Dec 9 '13 at 11:54
  • $\begingroup$ The following result is also an implication of Vandermonde's identity: $$\sum_{n=0}^\infty\left[\frac{(2n-3)!!}{(2n)!!}\right]^2=\frac4\pi$$ $\endgroup$ – Lucian Dec 9 '13 at 23:43

Notice how identity (1) takes the form:

$$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k} = (-1)^k\binom{k-(-n)-1}{k}$$

Compare with


It follows from (1) that

$$(-1)^{M-n}\binom{(M-n)-(M+k+1)-1}{M-n} = \binom{M+k+1}{M-n}$$

and hence



I hadn't noticed until today how straightforward it is to see how $\mathbf{(6,5)}$ are an instance of $(\mathbf{1})$. If you notice that the RHS of $$\binom{-n}{k}=(-1)^k\binom{n+k-1}{k}\tag{1}$$ hasn't many requirements, and allows for many possibilities to satisfy this form. The RHS allows any $k \in \mathbb{Z}^+$, has $k$ appear as the exponent to $(-1)$, and observe that $\binom{n+k-1}{k}$ only asks for some $n \in \mathbb{Z}$, and this imposes no relationship on $n, k$. So there isn't much special about $n \ \text{or}\ k$.

It does not take much to form an instance of $(\mathbb{1})$, so without much thought we can show that $(\mathbb{5})$ is an instance of the RHS of $(\mathbb{1})$ like so

Let $-n = M + k + 1, k = M - n$. Then $n + k - 1 = -(M+k+1)+(M-n)-1 = -k - n - 2$.

and without anything but variable assignments and substitution we have shown $(\mathbf 5, 6)$ are an instance of $(\mathbf{1})$. One might notice that the concluding statement $\binom{n+k+1}{k} = \binom{-k-n-2}{M - n}$ looks like a contradiction when we compare the binomial coefficients' indices, but keep in mind the $n$ defined in $(\mathbb{1})$ is not the same $n$ as in $(\mathbb{5,6})$, which is defined in the context of a larger $7$-step answer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.