Prove a binomial identity: $\sum_{i=1}^n i \binom{2n}{n-i}=\frac12(n+1) \binom{2n}{n-1}$

Question

I want to prove the product of even/odd power with a combinatorial number: \begin{aligned} \sum_{i=1}^n i \binom{2n}{n-i}&=\frac12(n+1) \binom{2n}{n-1}, \\ \sum_{i=1}^n i^2 \binom{2n}{n-i}&=2^{2n-2} n. \end{aligned} I am sure these results are correct since WolframAlpha verifies them. I wonder if the first formula can be proved, and also the general version can be proved: Formula related to combinatorial number.

---

Below is proof for the second formula:

First, note that $r\binom{n}{r}=n\binom{n-1}{r-1}$, and $\sum_{i=0}^n\binom{n}{i}=2^n$. We thus have \begin{aligned} \sum_{i=0}^n i\binom{n}{i}&=2^{n-1}n, \\ \sum_{i=0}^n i^2\binom{n}{i} &= \sum_{i=0}^n i(i-1)\binom{n}{i}+\sum_{i=0}^n i\binom{n}{i} \\ &= 2^{n-2}(n^2-n) + 2^{n-1} n \\ &= n(n+1)2^{n-2}. \end{aligned} Therefore, \begin{aligned} \sum_{i=0}^{2n}(n-i)^2\binom{2n}{i} &= n^2\sum_{i=0}^{2n}\binom{2n}{i}-2n\sum_{i=0}^{2n}i\binom{2n}{i}+\sum_{i=0}^{2n}i^2 \binom{2n}{i} \\ &= 2^{2n}n^2-2^{2n+1}n^2+n(2n+1)2^{2n-1} \\ &= 2^{2n-1} n, \end{aligned} and thus \begin{aligned} \sum_{i=0}^n i^2 \binom{2n}{n-i} = \sum_{i=0}^n (n-i)^2 \binom{2n}{i} = \frac12 \sum_{i=0}^{2n} (n-i)^2 \binom{2n}{i} = 2^{2n-2} n. \end{aligned}

Answer 1

\begin{align} \sum_{i=1}^n i\binom{2n}{n-i} &= \sum_{i=0}^n i\binom{2n}{n-i} \\ &= \sum_{i=0}^n (n-i)\binom{2n}{i} \\ &= n\sum_{i=0}^n \binom{2n}{i} - \sum_{i=1}^n i\binom{2n}{i} \\ &= \frac{n}{2}\left(\binom{2n}{n}+\sum_{i=0}^{2n} \binom{2n}{i}\right) - 2n\sum_{i=1}^n \binom{2n-1}{i-1} \\ &= \frac{n}{2}\left(\binom{2n}{n}+2^{2n}\right) - 2n\sum_{i=0}^{n-1}\binom{2n-1}{i} \\ &= \frac{n}{2}\left(\binom{2n}{n}+2^{2n}\right) - \frac{2n}{2}\sum_{i=0}^{2n-1}\binom{2n-1}{i} \\ &= \frac{n}{2}\left(\binom{2n}{n}+2^{2n}\right) - n2^{2n-1}\\ &= \frac{n}{2}\binom{2n}{n}\\ &= \frac{n+1}{2}\binom{2n}{n-1} \end{align}

Answer 2

I don't konw how to prove it, but for general case I found something:

Integral Representation and the Computation of Combinatorial Sums by G.P.EGORYCHEV Page77   says that:

---

verify the formula$\sum\limits_{i=1}^n i\left(\begin{array}{c} 2 n \\ n-i \end{array}\right)=\frac{1}{2}(n+1)\left(\begin{array}{c} 2 n \\ n-1 \end{array}\right)$ with Mathematica

Sum[Binomial[i, 1]*Binomial[2*n, n - i], {i, 1, n}]

$$ \frac{1}{2} (n+1) \binom{2 n}{n-1} $$

Answer 3

Let $$S_n=\sum_{k=0}^{n} {2n \choose k}$$ and let $$S'_n=\sum_{k=0}^{n} k {2n \choose n-k}=\sum_{k=0}^{n} (n-k) {2n \choose k}=nS_n-T_n$$ $$2^{2n}=\sum_{k=0}^{2n} {2n \choose k}=\sum_{k=0}^{n} {2n \choose k}+\sum_{k=n+1}^{2n} {2n \choose k}$$ $$\implies S_n+\sum_{k=n+1}^{2n} {2n \choose k}=2^{2n}$$ Change $k$ to $2n-j$, then $$S_n+\sum_{j=n-1}^{0} {2n \choose 2n-j}=2^{2n}$$ $$\implies S_n+ \sum_{j=0}^{n} {2n \choose j}-{2n \choose n}=2^{2n}$$ $$\implies S_n=2^{2n-1}+\frac{1}{2}{2n \choose n}.$$ Next let $$T_n=\sum_{k=0}^{n} k {2n \choose k}=\sum_{k=0}^{n} k\frac{(2n)!}{k!(2n-k)!}=2n\sum_{k=0}^{n}{2n-1 \choose k-1}=2n\sum_{j=0}^{n-1}{2n-1 \choose j} $$ We have $$2^{2n-1}= \sum_{k=0}^{2n-1} {2n-1\choose k}=\sum_{k=0}^{n-1} {2n-1 \choose k}+\sum_{k=n}^{2n-1} {2n-1 \choose k}=\sum_{k=0}^{n-1} {2n-1 \choose k}+\sum_{j=0}^{n-1} {2n-1 \choose n+j}$$ $$2^{2n-1}\implies \sum_{k=0}^{n-1} {2n-1 \choose k}+\sum_{j=0}^{n-1} {2n-1 \choose n+j}=\sum_{k=0}^{n-1} {2n-1 \choose k}+\sum_{j=0}^{n-1} {2n-1 \choose n-1-j}$$ $$\implies 2^{2n-1}= \sum_{k=0}^{n-1} {2n-1 \choose k}+\sum_{m=0}^{n-1} {2n-1 \choose m} \implies \sum_{k=0}^{n-1} {2n-1 \choose k}=2^{2n-2}$$ Finally, we have $$S'_n=n2^{2n-1}+\frac{n}{2} {2n \choose n}-n2^{2n-1}=\frac{n}{2}{2n \choose n}$$

Answer 4

Related Equation

Just for a fun alternative, we have the following equation that we will prove below.

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

Combinatorial Proof

One wish to colour $2n$ distinguishable balls such that exactly one is pink, some (can be none) are black, and some (can be none) are white. The two terms on LHS are, respectively:

1. Number of possible colouring such that there are at least $n+1$ black balls
2. Number of possible colouring such that there are at most $n-2$ white balls

Easy to see that (1) equals (2) so their difference is zero.

Relation to Original Question

$$ \begin{align} \sum_{i=1}^{n} i\binom{2n}{n-i} &= \frac{1}{2} \left[ \sum_{i=1}^{n} (n+i)\binom{2n}{n+i} - \sum_{i=1}^{n} (n-i)\binom{2n}{n-i} \right] \\\\ &= \frac{n+1}{2}\binom{2n}{n+1} \end{align} $$

Potential Extension

Instead of one pink, colour $m$ balls pink.

$$ \sum_{i=m+1}^{n}\binom{n+i}{m}\binom{2n}{n+i} - \sum_{i=1}^{n}\binom{n-i}{m}\binom{2n}{n-i} = 0 $$

The two terms are, respectively:

1. Number of possible colouring such that there are at least $n+1$ black balls.
2. Number of possible colouring such that there are at most $n-m-1$ white balls.

These two are the same, thus the difference is zero and we can write:

$$ \sum_{i=1}^{n}\left[\binom{n+i}{m}-\binom{n-i}{m}\right]\binom{2n}{n-i}= \sum_{i=1}^{m}\binom{n+i}{m}\binom{2n}{n-i} $$

For odd $m$, $\binom{n+i}{m}-\binom{n-i}{m}$ has the term $i^{m}$