Proving interesting identity with partial sums of Pascal's triangle rows

Question

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!

Answer 1

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).

Answer 2

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}$$

and

$$|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.