Closed form of a sum of binomial coefficients?

Question

I have the following function:

$T_n(d)=\sum\limits_{k=\frac{n-d}{2}}^{\lceil \frac{n}{2} \rceil}{k\choose \frac{n-d}{2}}$ ${n \choose 2k}$, where $n,d\in \mathbb{N}^0$, and $n,d$ have the same parity.

Looking at the sequences for various $d$, it seems that the formula is a polynomial of degree $d$ in $n$. This is speculation, but for example, where defined, it would appear that:

$T_{n}(1)=n$, $T_{n}(2)=\frac{1}{2}n^2$, $T_{n}(3)=\frac{1}{6}n^3-\frac{1}{6}n$, and $T_{n}(4)=\frac{1}{24}n^4-\frac{1}{6}n^2$

In fact, after further numerical testing, it seems that

$T_n(d)=\frac{n}{d!}\prod\limits_{j=1}^{d-1}(n-(2j-d))$

So my question is, is there a way to confirm the above results and show whether or not $T_n(d)$ is a polynomial of degree $d$ in $n$? If so, is there an intuitive reason why it is a polynomial with evenly spaced integer roots? The result seems rather elegant, if it's true.

EDIT: Simplifying the above expression, we have

$$T_n(d)=\frac{n}{d!}\prod\limits_{j=1}^{d-1}(n-(2j-d))=\frac{n}{d!}\frac{(n-1+(d-1))!!}{(n-1-(d-1))!!}=\frac{2^d n}{n+d}\cdot {\frac{n+d}{2} \choose d}$$

The third and fourth expressions in particular, seem like they would be very useful for a combinatorial proof. $n!!$ is the standard double factorial.

Answer 1

Here is a purely symbolic approach via the Snake Oil method. (See generatingfunctionology for more details). To make things simpler to read, note that $n=2m+d$ for some integer $m$ since $n$ and $d$ have the same parity. Hence the identity to be proven is equivalent to

$$T_n(d)=\sum\limits_{k}{k\choose m}{2m+d\choose 2k}=2^d \frac{2m+d}{2m+2d}{m+d\choose d} \tag{1}$$ The summation is over all integers $k$, with the understanding that ${n \choose k}=0$ unless $n\geq k\geq 0$.

To apply the Snake Oil method, we multiply the LHS by $x^d$ and sum over all $d$: $$\sum_{d,k} {k\choose m}{2m+d\choose 2k}x^d=\sum_k \binom{k}{m}\left[\sum_d\binom{2m+d}{2k}x^d\right]\tag{2}$$ The inner sum may be evaluated by shifting $d\to d-2m+2k$ to obtain

$$\sum_d\binom{d+2k}{2k}x^{d+2k-2m}=\frac{x^{2k-2m}}{(1-x)^{2k}}$$ where we have recalled the negative binomial series $(1-x)^{-n-1}=\sum_k \binom{k+n}{n} x^k$. This leaves the outer sum, which we shift by $k\to k+m$ to obtain

\begin{align} \sum_k \binom{k}{m} \frac{x^{2k-2m}}{(1-x)^{2k}} &=\sum_k \binom{k+m}{m} \frac{x^{2k}}{(1-x)^{2k+2m}} &(k\to k+2m) \\ &=\frac{1}{(1-x)^{2m}}\sum_k \binom{k+m}{m}\left(\frac{x^2}{(1-x)^2}\right)^k \\ &=\frac{1}{(1-x)^{2m}}\left[1-\frac{x^2}{(1-x)^2}\right]^{-m-1}&(\text{negative binomial series})\\ &=\frac{1}{(1-x)^{2m}}\left(\frac{(1-x)^2}{1-2x}\right)^{m+1}\\ &=\frac{1-x}{(1-2x)^{m+1}} \end{align}

So we have obtained the sum over $d$ in closed form. But we can expand this in a second way, using once again the negative binomial series:

\begin{align} \frac{1-x}{(1-2x)^{m+1}} &=(1-x)\sum_d \binom{m+d}{d}(2x)^d\\ &=\sum_d \binom{m+d}{d}(2x)^d-\sum_d \binom{m+d}{d}2^d x^{d+1}\\ &=\sum_d \binom{m+d}{d}(2x)^d-\sum_d \binom{m+d-1}{d-1}2^{d-1} x^{d}&(\text{$d\to d-1$ on 2nd term})\\ &=\sum_d \left[\binom{m+d}{m}-\frac12\binom{m+d-1}{m}\right](2x)^d \end{align}

The bracketed term simplifies upon factoring out the first binomial coefficient:

\begin{align} 1-\frac12\binom{m+d-1}{m} \binom{m+d}{m}^{-1} &=1-\frac12 \frac{(m+d-1)!}{m!(d-1)!}\cdot \frac{m!\,d!}{(m+d)!}\\ &=1-\frac12 \frac{d}{m+d}\\ &=\frac{2m+d}{2m+2d} \end{align} This yields the overall coefficient of $x^d$ as

$$2^d\frac{2m+d}{2m+2d}\binom{m+d}{m}$$

which by comparison with $(2)$ gives the desired identity.

Answer 2

There are two ways to prove your identity. The first way is to find some combinatorial interpretation of your sum, and show that it matches the more obvious combinatorial interpretation of your formula.

The other way, following your own suggestion, consists of three steps:

1. Show that the sum is a polynomial of degree $d$.
2. Find $d$ distinct roots of the polynomial by plugging them on the sum and showing that it evaluates to zero. Since the roots are distinct, this determine the polynomial up to a constant multiple.
3. Determine the constant by computing the sum at some valued of $n$ for which it doesn't vanish.

The first step is easy. First, notice that each $\binom{n}{n-2k} $ is a polynomial of degree $n-2k$ in $n$. Second, the associated factors can be written as $\binom{\ell+(n-d)/2}{\ell}$, where $\ell=k-(n-d)/2$, which is a polynomial of degree $\ell$ in $n$. The total degree of both factors is $n-2k+\ell=(n+d)/2-k\leq(n+d)/2-(n-d)/2=d$. This completes the first step.

The second step is complicated by the fact that we have to deal with negative binomial coefficients, though these can probably be avoided for the third step. I leave these two steps for you.

Answer 3

Another useful apparently classic technique uses basic complex variables.

Suppose we seek to evaluate $$\sum_{k\ge m} {k\choose m} {2m+d\choose 2k} = \sum_{k\ge m} {k\choose m} {2m+d\choose 2m+d-2k}$$ where the second binomial coefficient serves to delimit the upper bound of the range of $k$ which is finite.

Start from $${2m+d\choose 2m+d-2k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{2m+d-2k+1}} (1+z)^{2m+d} \; dz.$$

This gives the following integral for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k\ge m} {k\choose m} \frac{1}{z^{2m+d-2k+1}} (1+z)^{2m+d} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{2m+d+1}} \sum_{k\ge m} {k\choose m} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{2m+d+1}} \sum_{k\ge 0} {k+m\choose m} z^{2k+2m} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{d+1}} \sum_{k\ge 0} {k+m\choose m} z^{2k} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{2m+d}}{z^{d+1}} \frac{1}{(1-z^2)^{m+1}} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{m+d-1}}{z^{d+1}} \frac{1}{(1-z)^{m+1}} \; dz.$$

Extracting coefficients we obtain $$\sum_{q=0}^d {m+d-1\choose q} {d-q+m\choose m}.$$

Use another integral as in $${d-q+m\choose m} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{m+1}} (1+z)^{d-q+m} \; dz.$$ to obtain

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

The defining integral is zero for $m+d-1 \ge q>d$ so we may extend the sum to $m+d-1$, getting $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \sum_{q=0}^{m+d-1} {m+d-1\choose q} (1+z)^{-q}\; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \left(1+\frac{1}{1+z}\right)^{m+d-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^{d+m}}{z^{m+1}} \left(\frac{2+z}{1+z}\right)^{m+d-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1+z}{z^{m+1}} (2+z)^{m+d-1} \; dz.$$

We may now extract coefficients to obtain $$[z^m] (1+z) (2+z)^{m+d-1} = [z^m] (2+z)^{m+d-1} + [z^{m-1} ] (2+z)^{m+d-1} \\ = 2^{d-1} {m+d-1\choose m} + 2^d {m+d-1\choose m-1}.$$

This needs some re-writing to make it match the other answer. We get $$2^{d-1} {m+d-1\choose d-1} + 2^d {m+d-1\choose d} \\ = 2^{d-1} \frac{d}{m+d} {m+d\choose d} + 2^d \frac{m}{m+d} {m+d\choose d} \\ = 2^d {m+d\choose d} \left(\frac{1}{2} \frac{d}{m+d} + \frac{m}{m+d} \right) \\ = 2^d {m+d\choose d} \frac{2m+d}{2m+2d}.$$

Interesting exercise. There is another one like it at this MSE link.

Observe that these computations were done without intervention by a computer except to check arithmetic.

A trace as to when this method appeared on MSE and by whom starts at this MSE link.