As part of another problem I'm working on, I find myself needing to prove the following:

$$\sum_{k=0}^n\binom{2k+1}{k}\binom{m-(2k+1)}{n-k} = \sum_{k=0}^{n}\binom{m+1}{k}$$

where $n\leq m$. I've checked it computationally for all $n\leq m\leq 16$.

A few thoughts: this looks like a binomial convolution, but the $k$'s show up in the top of the binomial coefficients which disqualifies it from Vandermonde-esque identities I've found. Further, it uses weird binomial coefficients where the top is less than the bottom and the top can be negative - seems strange to me.

Some references I've found (for example) have similar looking sums of products, but the $2k$ instead of $k$ seems to hurt. Another ("Some Generalizations of Vandermonde's Convolution" by H. W. Gould) reveals to me that $$\sum_{k=0}^n\binom{2k+1}{k}\binom{m-(2k+1)}{n-k} = \sum_{k=0}^n\binom{2k+1+j}{k}\binom{m-(2k+1)-j}{n-k} $$ where $j$ can be any integer. Not sure if this can help.

I see from this question and elsewhere that partial sums of Pascal triangle rows don't really have closed forms. I can't think of how to use a generating function here (I'm trying to show a sum is equal to a sum), and the terms in each sum seem completely different. I'm not really sure how to proceed, any help/advice would be much appreciated!


2 Answers 2


This can be done by using Eq (18) in Jensen's "Sur une identité d'Abel et sur d'autres formules analogues", which states that

$$ \sum_{k=0}^n \binom{a+bk}{k}\binom{c-bk}{n-k} = \sum_{k=0}^n\binom{a+b-k}{n-k}b^k$$

Note that the RHS of my original equations satisfy the recurrences in Bernoulli's triangle, and proving that the RHS of Jensen's equation do as well is a bit more straightforward (boils down to Pascal's identity).


Here we seek to prove that

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

This is

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

Here $[z^n]$ enforces the range of the sum and we find

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^{n+1}} \sum_{k\ge 0} {2k+1\choose k} z^k (1+z)^{-2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w} \sum_{k\ge 0} \frac{(1+w)^{2k}}{w^k} z^k (1+z)^{-2k} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m-1}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w} \frac{1}{1-z(1+w)^2/w/(1+z)^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{w(1+z)^2-z(1+w)^2} \; dw \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{n+1}} \frac{1}{2\pi i} \int_{|w|=\gamma} \frac{1+w}{(1-wz)(w-z)} \; dw \; dz.$$

There is no pole at $w=0$ here. Note however that for the geometric series to converge we must have $|z(1+w)^2|\lt |w(1+z)^2|.$ We can achieve this by taking $\gamma = 2\epsilon$ so that

$$|z(1+w)^2| \le \epsilon (1+2\epsilon)^2 = \left. 4\epsilon^3 + 4\epsilon^2 + \epsilon \right|_{\epsilon=1/20} = \frac{242}{4000}$$


$$|w(1+z)^2| \ge 2\epsilon (1-\epsilon)^2 = \left. 2\epsilon^3 - 4\epsilon^2 + 2 \epsilon \right|_{\epsilon=1/20} = \frac{361}{4000}.$$

With these values the pole at $w=z$ is inside the contour and we get as the residue

$$\frac{1+z}{1-z^2} = \frac{1}{1-z}.$$

This yields on substitution into the outer integral

$$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+1}}{z^{n+1}} \frac{1}{1-z} \; dz = [z^n] \frac{(1+z)^{m+1}}{1-z} \\ = \sum_{k=0}^n [z^k] (1+z)^{m+1} [z^{n-k}] \frac{1}{1-z} = \sum_{k=0}^n {m+1\choose k}.$$

This is the claim.

Remark. For the pole at $w=1/z$ to be inside the contour we would need $1/\epsilon < 2\epsilon$ or $1< 2\epsilon^2$ which does not hold here so this pole does not contribute.


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.