5
$\begingroup$

$$\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.

$\endgroup$
9
$\begingroup$

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.

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

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}}.$$

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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}$.

$\endgroup$
1
$\begingroup$

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

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

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}$

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

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} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.