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 tried to solve this equation without success.
anyone know how to do it?

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

share|improve this question
    
I think this math.stackexchange.com/questions/618077/… must help you. –  user121270 May 25 at 22:20
    
"Identity" would be a more apt word that "equation". An identity is an equality that is true regardless of the values of any free variables (in this case, $n$ is free). "Equation" is usually (not quite always) means an equality in which you're trying to figure out which values of any free variables make it true. –  Michael Hardy May 25 at 22:21
    
. . . and I just noticed that although you said "prove" in the subject line, you said "solve" in the body of the question. What you're talking about here is proving an identity, not solving an equation. –  Michael Hardy May 26 at 2:33

3 Answers 3

A committee consists of $n$ Democrats and $n$ Republicans. You will randomly choose $k$ of the Democrats and $n-k$ of the Republicans for a subcommittee. The number of ways to do that is $$ \sum_{k=0}^n \binom n k \binom n {n-k} = \sum_{k=0}^n {\binom n k}^2. $$ The probability that you get exactly $k$ Democrats is $$ \frac{{\dbinom n k}^2}{\dbinom{2n}{n}} $$ since the denominator is the total number of ways to choose $n$ out of $2n$.

The expected number of Democrats is $n/2$, by symmetry. Hence $$ \sum_{k=0}^n k\Pr(\text{number of Democrats}=k) = \frac n 2. $$ Thus $$ \sum_{k=0}^n k {\binom n k}^2 = \frac n 2 \binom{2n}{n}. $$

Finally, note that

$$\binom{2n}{n}=\binom{2n-1}{n}+\binom{2n-1}{n-1}=2\binom{2n-1}{n-1}$$

using standard identities for binomial coefficients.

share|improve this answer
    
the right side of your identity is not equal to what I wrote in the question. can I ask why? –  user144555 May 25 at 22:51
    
@Michael, I fixed a small error and added some explanation to address the query in the OP's comment. I hope you're OK with the edit. –  Barry Cipra May 25 at 23:24
    
I think Barry Cipra's edit may deal with the first comment above, except for this: never conclude that two things are not equal merely because they don't immediately look the same. –  Michael Hardy May 26 at 1:00

Here's an approach using generating functions. By the binomial theorem, $$ \sum_{k=0}^n \binom{n}{k} x^k = (1 + x)^n \, . $$ Differentiating the above and then multiplying by $x$, we have $$ \sum_{k=0}^n k \binom{n}{k} x^{k} = nx(1+x)^{n-1} \, . $$ Let $[x^m] f(x)$ denote the coefficient of $x^m$ in $f(x)$. By the convolution formula for ordinary generating functions, then \begin{align*} \sum_{k=0}^n k \binom{n}{k}^2 &=\sum_{k=0}^n k \binom{n}{k} \binom{n}{n-k}= [x^n] \left(nx(1+x)^{n-1}\right) (1+x)^n\\ &= [x^{n-1}] n (1+x)^{2n-1} = n \binom{2n-1}{n-1} \end{align*} as desired.

share|improve this answer

And here's another proof using binomial theorem. Let $$S=\sum\limits_{k=0}^n k {n \choose k}^2$$ Therefore $$S=0 {n \choose 0}^2+1 {n \choose 1}^2 + \cdots + n {n \choose n}^2$$ Since ${n \choose k}={n \choose n-k}$, we can reverse the sum and add it to itself, which gives us $$2S=(0+n ){n \choose 0}^2+ (1+(n-1)) {n \choose 1}^2 + \cdots + (n+0 ){n \choose n}^2$$ $$2S=n \left( {n \choose 0}^2+ {n \choose 1}^2 + \cdots + {n \choose n}^2 \right)$$

Now, look at the binomial expansion of $(1+x)^n$ and $(x+1)^n$. $$(1+x)^n={n \choose 0}x^0+{n \choose 1}x^1 + \cdots + {n \choose n}x^n$$ $$(x+1)^n={n \choose 0}x^n+{n \choose 1}x^{n-1} + \cdots + {n \choose n}x^0$$ It's clear now that in the product of the above 2 expressions, the coeffecient of $x^n$ will be $$ {n \choose 0}^2+ {n \choose 1}^2 + \cdots + {n \choose n}^2$$. Therefore $$ {n \choose 0}^2+ {n \choose 1}^2 + \cdots + {n \choose n}^2= {2n \choose n}$$ Hence $$S=\frac{n}{2}{2n \choose n}=n{2n-1 \choose n-1}$$

share|improve this answer

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.