Prove that $\sum_{n=0}^N\binom{2N-n}N2^n(n+1)=(1+2N)\binom{2N}N$

I used WolframAlpha to calculate a sum but it didn't show me the way :( Anybody has a hint or a solution for proving this sum? $$\sum_{n=0}^N\binom{2N-n}N2^n(n+1)=(1+2N)\binom{2N}N$$

Solution 1:

$$\begin{align} \sum_{n=0}^N\binom {2N-n}N2^n(n+1) &=\sum_{n=0}^N\binom {2N-n}N\sum_{j=0}^n \binom nj(n+1) &&\scriptsize\text{using }\sum_{j=0}^n \binom nj=2^n\\ &=\sum_{n=0}^N\binom {2N-n}N\sum_{j=0}^n \binom {n+1}{j+1}(j+1)\\ &=\sum_{n=0}^N\binom {2N-n}N\sum_{j=1}^{n+1} \binom {n+1}{j}j\\ &=\sum_{j=1}^{N+1}j\sum_{n=0}^{j-1}\binom {2N-n}N\binom {n+1}j &&\scriptsize (0\le n<j\le N+1)\\ &=\sum_{j=1}^{N+1}j\binom {2N+2}{N+1+j} &&\scriptsize \text{using}\sum_n\binom {a-n}b\binom {c+n}d=\binom{a+c+1}{b+d+1}\\ &=\frac 12(N+1)\binom {2N+2}{N+1} &&\scriptsize\text{using (*) }\\ &=\frac 12(N+1)\cdot \frac {2N+2}{N+1}\cdot \binom {2N+1}{N}\\ &=(N+1)\cdot \binom {2N+1}{N+1}\\ &=(N+1)\cdot\frac {2N+1}{N+1}\cdot \binom {2N}N\\ &=\color{red}{(1+2N)\binom {2N}N}\qquad \blacksquare \end{align}$$

*See derivation below. Putting $n=N+1$ gives the result used above. $$\small\begin{align} \sum_{r=1}^n\binom{2n}{n+r}r &=\sum_{j=n+1}^{2n}\binom {2n}j(j-n)\\ &=\sum_{j=n+1}^{2n}\binom {2n}jj-n\sum_{j=n+1}^{2n}\binom {2n}j\\ &=n2^{2n-1}-n\cdot \frac 12\left(\left(\sum_{j=0}^{2n}\binom {2n}j\right)-\binom {2n}n\right)\\ &=n2^{2n-1}-\frac 12n\left(2^{2n}-\binom {2n}n\right)&& \hspace{2.5cm}\\ &=\frac 12n\binom {2n}n\end{align}$$ Note that $$\begin{align} \frac 12(n+1)\binom {2n}{n+1} &=\frac 12 (n+1)\frac {(2n)!}{(n+1)!(n-1)!}\\ &=\frac 12 \cdot \frac {(2n)!}{n!(n-1)!}\cdot\color{grey}{ \frac nn} \qquad\hspace{3cm}\\ &=\frac 12 n\cdot \frac {(2n)!}{n!n!}\\ &=\frac 12 n\binom {2n}n \end{align}$$

Note also that $$\small\begin{align} \sum_{n}\binom {a-n}b\binom {c+n}d &=\sum_n\binom {a-n}{a-b-n}\binom {c+n}{c+n-d}\\ &=\sum_n(-1)^{a-b-n}\binom {-b-1}{a-b-n}(-1)^{c+n-d}\binom {-d-1}{c+n-d} &&\text{(upper negation)}\\ &=(-1)^{a-b+c-d}\sum_n\binom {-b-1}{a-b-n}\binom {-d-1}{c-d+n}\\ &=(-1)^{a-b+c-d}\binom {-b-d-2}{a-b+c-d} &&\text{(Vandermonde)}\\ &=(-1)^{a-b+c-d}(-1)^{a-b+c-d}\binom {a+c+2-1}{a-b+c-d} &&\text{(upper negation)}\\ &=\binom {a+c+1}{a-b+c-d}\\ &=\binom {a+c+1}{b+d+1}\end{align}$$

Solution 2:

Starting from

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

we write

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

We may extend $n$ to infinity beyond $N$ because the sum term does not contribute to the coefficient extractor in that case, getting

$$[z^N] (1+z)^{2N} \sum_{n\ge 0} 2^n (n+1) z^n (1+z)^{-n} = [z^N] (1+z)^{2N} \frac{1}{(1-2z/(1+z))^2} \\ = [z^N] (1+z)^{2N+2} \frac{1}{(1-z)^2}.$$

Extracting the coefficient we find

$$\sum_{q=0}^N {2N+2\choose q} (N+1-q).$$

The first piece here is

$$(N+1) \sum_{q=0}^N {2N+2\choose q} = (N+1) \frac{1}{2} \left(2^{2N+2} - {2N+2\choose N+1}\right).$$

The second piece is

$$\sum_{q=1}^N {2N+2\choose q} q = (2N+2) \sum_{q=1}^N {2N+1\choose q-1} \\ = (2N+2) \sum_{q=0}^{N-1} {2N+1\choose q} = (2N+2) \frac{1}{2} \left(2^{2N+1} - {2N+1\choose N} - {2N+1\choose N+1} \right).$$

Joining the two pieces the powers of two cancel and we are left with

$$(2N+2) {2N+1\choose N} - \frac{1}{2} (N+1) {2N+2\choose N+1} \\ = (2N+2) \frac{2N+1}{N+1} {2N\choose N} - \frac{1}{2} (N+1) \frac{2N+2}{N+1} {2N+1\choose N} \\ = 2 (2N+1) {2N\choose N} - (N+1) \frac{2N+1}{N+1} {2N\choose N} \\ = (2N+1) {2N\choose N}$$

as claimed.