Find a simple formula for $\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+…+\binom{n}{n-1}\binom{n}{n}$

$$\binom{n}{0}\binom{n}{1}+\binom{n}{1}\binom{n}{2}+...+\binom{n}{n-1}\binom{n}{n}$$

All I could think of so far is to turn this expression into a sum. But that does not necessarily simplify the expression. Please, I need your help.

First note that $\dbinom{n}k = \dbinom{n}{n-k}$. Hence, your sum can be written as $$\sum_{k=0}^{n-1} \dbinom{n}k \dbinom{n}{k+1} = \sum_{k=0}^{n-1} \dbinom{n}k \dbinom{n}{n-k-1}$$ Now consider a bag with $n$ red balls and $n$ blue balls. We want to choose a total of $n-1$ bals. The total number of ways of doing this is given by $$\dbinom{2n}{n-1} \tag{\star}$$ However, we can also count this differently. Any choice of $n-1$ balls will involve choosing $k$ blue balls and $n-k-1$ red balls. Hence, the number of ways of choose $n-1$ balls with $k$ blue balls is $$\color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-1-k}}$$ Now to count all possible ways of choosing $n-1$ balls, we need to let our $k$ run from $0$ to $n-1$. Hence, the total number of ways is $$\sum_{k=0}^{n-1} \color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-k-1}} \tag{\dagger}$$ Now since $(\star)$ and $(\dagger)$ count the same thing, they must be equal and hence, we get that $$\sum_{k=0}^{n-1} \color{blue}{\dbinom{n}k} \color{red}{\dbinom{n}{n-k-1}} = \dbinom{2n}{n-1}$$

EDIT As Brian points out in the comments, the above is a special case of the more general Vandermonde's identity. $$\sum_{k=0}^r \dbinom{m}k \dbinom{n}{r-k} = \dbinom{m+n}r$$ The proof for this is essentially the same as above. Consider a bag with $m$ blue balls and $n$ red balls and count the number of ways of choosing $r$ balls from these $m+n$ balls in two different ways as discussed above.

• Love the formatting! +1 – Macavity Apr 4 '13 at 18:32
• (+1) Nicely explained. You might want to mention that it’s a case of Vandermonde’s identity, which has essentially the same proof. – Brian M. Scott Apr 4 '13 at 18:43
• Thanks so much!!!! Your explanation was great!!!! – Dome Apr 4 '13 at 18:49

We have $$\sum_{k=0}^{n-1}\dbinom{n}{k}\dbinom{n}{k+1}=\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n}{k+1}=\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n}{n+1-k}=\color{red}{\dbinom{2n}{n+1}}$$ by the Chu-Vandermonde identity and since $\dbinom{n}{n}\dbinom{n}{n+1}=0$. Another way is to use the integral representation of the binomial coefficient $$\dbinom{n}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{k+1}}dz$$ and get $$\sum_{k=0}^{n}\dbinom{n}{k}\dbinom{n}{k+1}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{2}}\sum_{k=0}^{n}\dbinom{n}{k}z^{-k}dz$$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{n}}{z^{2}}\left(1+\frac{1}{z}\right)^{n}dz=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{2n}}{z^{n+2}}dz=\color{blue}{\dbinom{2n}{n+1}}.$$

There is a simple combinatorial interpretation. Assume that you have a parliament with $n$ politicians in the left wing and $n$ politicians in the right wing. If you want to select a committee made by $n-1$ politicians, you obviously have $\binom{2n}{n-1}=\binom{2n}{n+1}$ ways for doing it. On the other hand, by classifying the possible committees according to the number of politicians of the left wing in them, you have: $$\binom{2n}{n-1}=\sum_{l=0}^{n-1}\binom{n}{l}\binom{n}{n-1-l} = \sum_{l=0}^{n-1}\binom{n}{l}\binom{n}{l+1}$$ as wanted.

Hint: it's the coefficient of $T$ in the binomial expansion of $(1+T)^n(1+T^{-1})^n$, which is equivalent to saying that it's the coefficient of $T^{n+1}$ in the expansion of $(1+T)^n(1+T^{-1})^nT^n=(1+T)^{2n}$.

$\newcommand{\bbx}{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}{\mathcal{#1}} \newcommand{\mrm}{\mathrm{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$

Note that $\ds{{n \choose k} + {n \choose k + 1} = {n + 1 \choose k + 1}}$

\begin{align} \sum_{k = 0}^{n - 1}{n \choose k}{n \choose k + 1} & = \sum_{k = 0}^{n - 1} {\bracks{{n \choose k} + {n \choose k + 1}}^{\,2} - {n \choose k}^{2} - {n \choose k + 1}^{2}\over 2} \\[5mm] & = {1 \over 2}\sum_{k = 0}^{n - 1}{n + 1 \choose k + 1}^{2} - {1 \over 2}\sum_{k = 0}^{n - 1}{n \choose k}^{2} - {1 \over 2}\sum_{k = 0}^{n - 1}{n \choose k + 1}^{2} \\[5mm] & = {1 \over 2}\sum_{k = 1}^{n}{n + 1 \choose k}^{2} - {1 \over 2}\sum_{k = 0}^{n - 1}{n \choose k}^{2} - {1 \over 2}\sum_{k = 1}^{n}{n \choose k}^{2} \\[5mm] & = {1 \over 2}\bracks{\sum_{k = 0}^{n + 1}{n + 1 \choose k}^{2} -2} - {1 \over 2}\bracks{\sum_{k = 0}^{n}{n \choose k}^{2} - 1} - {1 \over 2}\bracks{\sum_{k = 0}^{n}{n \choose k}^{2} - 1} \\[5mm] & = {1 \over 2}{2n + 2 \choose n + 1} - {2n \choose n} \end{align} where I used the well known result $\bbx{\ds{\quad\sum_{i = 0}^{m}{m \choose i}^{2} = {2m \choose m}}}$. Moreover, \begin{align} \sum_{k = 0}^{n - 1}{n \choose k}{n \choose k + 1} & = {1 \over 2}\,{\pars{2n + 2}\pars{2n + 1}\pars{2n}! \over \pars{n + 1}n!\pars{n + 1}n!} - {2n \choose n} = \pars{{2n + 1 \over n + 1} - 1}{2n \choose n} \\[5mm] & = {n \over n + 1}{2n \choose n} = {n \over n + 1}{\pars{2n}! \over n!\,n!} = {\pars{2n}! \over \pars{n + 1}!\pars{n - 1}!} = \bbx{\ds{2n \choose n + 1}} \end{align}

• It is not easy to add a new perspective to a popular sum like this one. Upvoted for originality of the approach. (+1): – Marko Riedel Feb 1 '17 at 23:24
• @MarkoRiedel Thanks. Cross terms always suggest this approach. It's useful too for products of $\log$'s, etc... – Felix Marin Feb 2 '17 at 0:14

Rewrite the sum as $\displaystyle\sum_0^{n-1}\binom{n}{k}\binom{n}{k+1}$, then by combinatorial interpretation, this is: $$\sum_{0}^{n-1}\binom{n}{k}\binom{n}{k+1}=\binom{2n}{2k+1}$$

The right hand side $\binom{2n}{2k+1}$ is the number of ways to choose $2k+1$ from a total of $2n$. For the left hand side, divide $2n$ into two groups of size $n$ of each, then if choose $k$ from one group, then must choose $2k+1-k=k+1$ from another group, sum over all possible $k$, then you get $\sum_0^{n-1}\binom{n}{k}\binom{n}{k+1}$

• What is $k$ in the rhs? – Julien Apr 4 '13 at 18:28
• I have downvoted this answer for being (mathematically) unintelligible. – anon Apr 5 '13 at 0:51

Using the estimate derived in this answer, we get \begin{align} \sum^{n-1}_{j=0}\binom{n}{j}\binom{n}{j+1} &=\sum^{n-1}_{j=0}\binom{n}{n-j}\binom{n}{j+1}\\ &=\binom{2n}{n+1}\\ &=\binom{2n}{n}\frac{n}{n+1}\\[3pt] &\sim\frac{4^n}{\sqrt{\pi n}}\left(1-\frac9{8n}\right) \end{align}