I cannot prove that $ \sum_{k=0}^n \sum_{i=k}^n {n \choose k} {n+1 \choose i+1} = 2^{2n} $

Question

I 've tried to calculate the internal sum first with no success. $$ \sum_{k=0}^n \Bigg( {n \choose k} \sum_{i=k}^n {n+1 \choose i+1} \Bigg) = 2^{2n} $$ Thank you in advance

Answer 1

Let the sum in question be $S$. Then $$S = \sum_{k=0}^n \sum_{i=k+1}^{n+1} \binom{n}{k} \binom{n+1}{i} = \sum_{k=0}^n \sum_{i=k+1}^{n+1} \binom{n}{n-k} \binom{n+1}{n+1-i} = \sum_{k=0}^n \sum_{i=0}^k \binom{n}{k} \binom{n+1}{i}$$ where in the third step we re-index the sum using $n-k \mapsto k$ and $n+1-i \mapsto i$. Adding the first and third expressions, we get $$2S = \sum_{k=0}^n \sum_{i=0}^{n+1} \binom{n}{k} \binom{n+1}{i} = \left(\sum_{k=0}^n \binom{n}{k} \right) \left(\sum_{i=0}^{n+1} \binom{n+1}{i}\right) = 2^n \cdot 2^{n+1} = 2^{2n+1}.$$

Answer 2

$$ \begin{align} \sum_{k=0}^n\sum_{j=k}^n\binom{n}{k}\binom{n+1}{j+1} &=\sum_{k=0}^n\sum_{j=k}^n\binom{n}{k}\left[\binom{n}{j+1}+\binom{n}{j}\right]\tag1\\ &=\sum_{k=0}^n\sum_{j=k}^n\binom{n}{k}\binom{n}{j+1}+\sum_{k=0}^n\sum_{j=k}^n\binom{n}{k}\binom{n}{j}\tag2\\ &=\sum_{k=0}^n\sum_{j=k}^n\binom{n}{k}\binom{n}{j+1}+\sum_{j=0}^n\sum_{k=0}^j\binom{n}{k}\binom{n}{j}\tag3\\ &=\sum_{k=0}^n\sum_{j=k+1}^n\binom{n}{k}\binom{n}{j}+\sum_{k=0}^n\sum_{j=0}^k\binom{n}{k}\binom{n}{j}\tag4\\ &=\sum_{k=0}^n\sum_{j=0}^n\binom{n}{k}\binom{n}{j}\tag5\\ &=\sum_{k=0}^n\binom{n}{k}\,\sum_{j=0}^n\binom{n}{j}\tag6\\[9pt] &=2^n\,2^n\tag7 \end{align} $$ Explanation:
$(1)$: Pascal Triangle recursion
$(2)$: distributive property
$(3)$: change order of summation in the righthand sum
$(4)$: substitute $j\mapsto j-1$ in the lefthand sum
$\phantom{(4)\text{:}}$ swap $j$ and $k$ in the righthand sum
$(5)$: combine sums
$(6)$: distributive property
$(7)$: write $(1+1)^n$ as a binomial sum twice

Answer 3

Let $[z^a]f(z)$ denote the $z^a$ coefficient in $f(z)$. The double-sum rearranges to$$\sum_{i=0}^n\sum_{k=0}^i[x^k][y^{i+1}](1+x)^n(1+y)^{n+1},$$i.e. the sum of coefficients of all terms in $(1+x)^n(1+y)^{n+1}$ for which the $x$ exponent is less than the $y$ exponent. Of the $2^{2n+1}$ terms obtained by expanding the brackets, we seek to prove exactly half meet that condition. Each such terms is characterized by which if any of the $1+x$ factors has its $x$ chosen, and which if any of the $1+y$ factors has its $y$ chosen. We can pair the terms with those in which the choice is reversed, e.g. the $xy^2$ term in the case $n=1$, due to the $x$ and both $y$s being chosen, pairs with the $1$, where the $x$ and both $y$s are not chosen. In each such pair of conjugates, exactly one has $y$s outnumbering $x$s, so we're done.