Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have to give a combinatorial proof of

$$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$

I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have algorithms to solve most problems. Usually I won't just "see" solutions unless I have a thorough enough understanding of a theory. This is also the case here. I know what the symbols mean, but I don't see what I should count and how to obtain the identity.

I think the right-hand side counts $n$-element subsets of a $(2n-1)$-element set with one element chosen to be "special". I think I should find a partition of the set of such subsets into $n$ parts so that the left-hand side is the sum of the cardinalities of the parts. Is there $n$ of anything on the right-hand side? Well, there are $n$ choices for the "special" elements, but only after I've chosen the $n$-element subset. Otherwise I can choose the "special element" in $2n-1$ ways.

This is a homework problem so I probably shouldn't ask for a full solution. But I would like to have some guidelines for approaching such problems, perhaps based on this example.

share|improve this question

5 Answers 5

up vote 11 down vote accepted

It seems easier to look at the left-hand side :

$\sum \binom n k ^2 = \binom {2n} n$ is the number of ways to choose $n$ elements out of a set $X$ of $2n$ elements, where we are given a partition $X = X_1 \cup X_2$ with $\# X_i = n$.
Next, $\sum k \binom n k ^2$ is the number of ways to do this and then choose a special element among the ones chosen in $X_1$. So, reversing the order of the choices (choose the special element first), then forgetting as much as possible about the partition, you get that is the number of ways to pick one special element in $X_1$ and then pick $n-1$ other elements in $X$.

Then it shouldn't be too hard to explain why this is equal to the right-hand side.

share|improve this answer
    
Nice approach, +1. –  1015 Feb 24 '13 at 14:40
    
Out of curiosity, is there a combinatorial proof that $\sum \binom{n}{k}^2 = \binom{2n}{n}$ ? –  user54147 Feb 24 '13 at 15:58
2  
@LevLivnev : as hinted, $\binom n k ^2 = \binom n k \binom n {n-k}$ is the number of ways to choose $k$ elements in $A_1$ and $n-k$ elements in $A_2$. When you forget about the partition, this sum is the number of ways to choose $n$ elements in $A_1 \cup A_2$, which is of size $2n$. –  mercio Feb 24 '13 at 16:02

Since $\binom{n}{k} = \dfrac{n}{k}\binom{n-1}{k-1}$ the identity can be written as $$\sum_{k=1}^n\binom{n}{n-k}\binom{n-1}{k-1} = \binom{2n-1}{n-1}.$$

Suppose we have $2n-1$ items in line and we need to choose $n-1$ items from them. The right hand side is the number of ways to do this in the obvious way. Another way to choose our $n-1$ items from this line: Divide the line into two sections; the first section contains the first $n$ items, the second contains the last $n-1$ items. When picking $n-1$ items from the entire line, we could pick all $n-1$ from the first line and none from the second ($k=1$), or $n-2$ from the first line and $1$ from the second ($k=2$) ... ... or none from the first line and $n-1$ from the second ($k=n$).

share|improve this answer
    
I don't understand this solution. I think the identity is ${n\choose k}={n\over k}{n-1\choose k-1}.$ But then I get $$\sum_{k=1}^nk\cdot{n\over k}{n\choose n-k}{n-1\choose k-1}=n{2n-1\choose n}$$ or $$\sum_{k=1}^n{n\choose n-k}{n-1\choose k-1}={2n-1\choose n},$$ which is different from what you wrote. –  Bartek Mar 3 '13 at 23:31
    
@Bartek Remember that $\binom{n}{k} = \binom{n}{n-k}.$ –  Ragib Zaman Mar 4 '13 at 2:19
    
Oh! Right. But still the identity at the beginning of your post needs to be edited I think. Thank you for the solution. –  Bartek Mar 4 '13 at 2:23

For $a,b,n \in \mathbb{N}$ we have

$$\binom{a+b}{n} = \sum_{p+q=n} \binom{a}{p} \cdot \binom{b}{q}$$

since both sides count the subsets of $\{1,\dotsc,a\} \sqcup \{1,\dotsc,b\}$ with $n$ elements. This could also be derived from the isomorphism $\Lambda^n(V \oplus W) = \bigoplus_{p+q=n} \Lambda^p(V) \otimes \Lambda^q(W)$ of exterior powers, where $V,W$ are free modules of rank $a$ resp. $b$ (decategorification).

In particular,

$$\sum_{k=0}^{n} k \binom{n}{k}^2 = n \sum_{k=0}^{n} \binom{n}{n-k} \binom{n-1}{k-1}=n \binom{2n-1}{n-1}=n \binom{2n-1}{n}.$$

One can also derive a lot of other formulas as a special case, for example

$$\sum_{k=0}^{n} \binom{n}{k}^2 = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \binom{2n}{n}.$$

share|improve this answer

Since you said you'd prefer a hint, I will show you how a related problem is approached. In retrospect I can see that this is not what is meant by a combinatorial proof, but maybe it will still be helpful.

Suppose you want to prove that: $$\sum^n_{s=0} \binom{n}{s}^2 = \binom{2n}{n}$$ To do the above, consider the binomial expansions of both sides of: $$(1+x)^n(1+x)^n = (1+x)^{2n}$$ (i.e. expand the RHS binomially and expand both parts of the LHS binmially and write out the product).

I have not verified it yet but I believe a similar approach may work for the problem you provided, as long as you choose an appropriate identity to start with.

share|improve this answer
    
combinatorial proof generally means proof by counting arguments. this might be of use. –  user45099 Feb 24 '13 at 14:41
    
@user1709828 you're right, this is far from combinatorial. I couldn't think of a more direct way so I guess I'll just leave this here for reference. –  user54147 Feb 24 '13 at 15:21
    
Also I think it may be useful since it suggests how to prove the assertion that is made at the beginning of mercio's answer. –  user54147 Feb 24 '13 at 15:22
    
in a non-combinatorial way. –  user54147 Feb 24 '13 at 17:04
    
But actually these kinds of proofs hold in every symmetric monoidal category with direct sums, in particular for the category of (finite) sets, and thus is a "bijective proof" in disguise. See also the wonderful paper "From natural numbers to Feynman diagrams" by Baez and Dolan. –  Martin Brandenburg Mar 4 '13 at 2:33

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ $\ds{\sum_{k = 1}^{n}k{n \choose k}^{2} = n{2n - 1 \choose n}:\ {\large ?}}$

\begin{align}&\sum_{k = 1}^{n}k{n \choose k}^{2} =\sum_{k = 1}^{n}k{n \choose k}\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z}\sum_{k = 1}^{n}k{n \choose k}\pars{1 \over z}^{k} \,{\dd z \over 2\pi\ic} \end{align}

Note that $\ds{\sum_{k = 1}^{n}k{n \choose k}a^{k} =a\,\partiald{}{a}\sum_{k = 0}^{n}{n \choose k}a^{k} =a\,\partiald{\pars{1 + a}^{n}}{a} = na\pars{1 + a}^{n - 1}}$ such that

\begin{align} &\color{#66f}{\large\sum_{k = 1}^{n}k{n \choose k}^{2}} =\oint_{\verts{z}\ =\ 1} {\pars{1 + z}^{n} \over z}\bracks{n\,{1 \over z}\,\pars{1 + {1 \over z}}^{n - 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=n\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n - 1} \over z^{n + 1}} \,{\dd z \over 2\pi\ic} =\color{#66f}{\large n{2n - 1 \choose n}} \end{align}

share|improve this answer
    
Dat ternary operator. –  octatoan Sep 6 at 7:15

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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