1
$\begingroup$

I have been given an identity $\begin{align} \sum_{i=0}^n i\binom{n}{i}^2 = n\binom{2n-1}{n-1} \end{align}$. However when I tried to prove it, I got a different result. $\begin{align} \sum_{i=0}^n i\binom{n}{i}^2 = n\sum_{i=0}^n \binom{n-1}{i-1} \binom{n}{i} = n\sum_{i=0}^n \binom{n-1}{n-i} \binom{n}{i} = n\binom{2n-1}{n} \end{align}$

First equation follows from absorption identity, second one from symmetry, and the third one from Vandermonde's identity. Where is my mistake?

$\endgroup$
  • 1
    $\begingroup$ I think you'd find that $\binom{n}{k}=\binom{n}{n-k}$ that should help to some extent. $\endgroup$ – user451844 Aug 11 '17 at 16:56
3
$\begingroup$

Let us devise a purely combinatorial approach: assume to have a parliament with $n$ people in the right wing, $n$ people in the left wing. In how many ways can we form a committee with $n$ people and elect a chief of the commitee from the left wing? The first approach is to select $i$ people from the left wing, $n-i$ people from the right wing, then the chief among the selected $i$ people from the left wing. This leads to $\sum_{i=0}^{n}i\binom{n}{i}\binom{n}{n-i}=\sum_{i=0}^{n}i\binom{n}{i}^2$. The other approach is to select the chief from the left wing first ($n$ ways for doing that), then select $n-1$ people from the remaining $2n-1$ in the parliament. Conclusion: $$ \sum_{i=0}^{n}i\binom{n}{i}^2 = n\binom{2n-1}{n-1} = n\binom{2n-1}{n}. $$

$\endgroup$
  • 1
    $\begingroup$ +1 for making me realize (along with @Roddy MacPhee) that $2n-1-(n-1)=n$ :P $\endgroup$ – Joald Aug 11 '17 at 17:09
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}$ \begin{align} \sum_{i = 0}^{n}i{n \choose i}^{2} & = \sum_{i = 0}^{n}i{n \choose i}{n \choose n - i} = \sum_{i = 0}^{n}i{n \choose i}\bracks{z^{n - i}}\pars{1 + z}^{n} = \bracks{z^{n}}\pars{1 + z}^{n}\sum_{i = 0}^{n}{n \choose i}i\,z^{i} \\[5mm] & = \bracks{z^{n}}\pars{1 + z}^{n} \bracks{z\,\partiald{}{z}\sum_{i = 0}^{n}{n \choose i}z^{i}} = \bracks{z^{n}}\pars{1 + z}^{n}\bracks{z\,\partiald{\pars{1 + z}^{n}}{z}} \\[5mm] & = \bracks{z^{n - 1}}\pars{1 + z}^{n}\bracks{n\pars{1 + z}^{n - 1}} = n\bracks{z^{n - 1}}\pars{1 + z}^{2n - 1} = \bbx{n{2n - 1 \choose n - 1}} \end{align}

$\endgroup$
0
$\begingroup$

If one takes $n=2$ then $$\sum_{i=0}^n i\binom{n}i^2=0+\binom21^2+2\binom22^2=4+2=6$$ and $$\binom{2n-1}{n-1}=\binom{3}1=3.$$ It seems in this case that $\sum_{i=0}^n i\binom{n}i^2$ equals $n\binom{2n-1}n$ rather than $\binom{2n-1}{n-1}$.

$\endgroup$
0
$\begingroup$

The question as stated is incorrect; here's a combinatorial proof for your version (the $n\binom{2n-1}{n}$ version):

Suppose we have $n$ turtles and $n$ rabbits at a sports meet. How many ways can we choose two teams of $n$ animals each, one of which has a captain (who must be a turtle)?

The LHS counts this directly by counting the number of ways to choose $i$ turtles to include and $i$ rabbits to exclude from the team with a captain, and picking a captain from among these turtles. The other team is composed of the remaining animals.

The RHS first picks the captain, then chooses $n$ of the other animals to form the other team. The remaining animals join the captain's team.

$\endgroup$
  • 1
    $\begingroup$ the two results are the same $\endgroup$ – G Cab Aug 11 '17 at 17:17

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.