Guys, I'm trying to prove that [math]\sum ^{n}_{k=1}k\binom{n}{k}^2= n\binom{2n-1}{n-1}[/math]And at the n+1th step I'm doing this [math]\sum ^{n+1}_{k=1}k\binom{n}{k}^2=\sum ^{n}_{k=1}k\binom{n}{k}^2+ k\binom{n}{k}^2[/math] and then I'm using the inductive hypothesis and I'm getting:[math]n\binom{2n-1}{n-1}+[/math] and I'm stuck right here I don't know how to write [imath]k\binom{n}{k}^2[/imath], can someone tell me what am I doing wrong.
Proof by induction
- Thread starter Albi
- Start date
topsquark
Senior Member
- Joined
- Aug 27, 2012
- Messages
- 2,269
On the second line, the k in the second term on the RHS is n + 1. And I you also have to change the n in the upper "index" of the binomial coefficient when you go up one:
[math]\sum_{k = 1}^{n + 1} k {n + 1 \choose k} ^2 = \sum_{k = 1}^{n} k {n + 1 \choose k} ^2 + (n + 1) {n + 1 \choose n + 1 } ^2[/math]
-Dan
[math]\sum_{k = 1}^{n + 1} k {n + 1 \choose k} ^2 = \sum_{k = 1}^{n} k {n + 1 \choose k} ^2 + (n + 1) {n + 1 \choose n + 1 } ^2[/math]
-Dan
How do I use the inductive hypothesis then?
topsquark
Senior Member
- Joined
- Aug 27, 2012
- Messages
- 2,269
Someone is going to have to be more clever than me.
[math]{n + 1 \choose k} = \dfrac{(n + 1)!}{k! (n + 1 - k)!} = \dfrac{(n + 1) n!}{k! (n + 1 - k) (n - k)!} = \dfrac{n + 1}{n + 1 - k} {n \choose k}[/math]
If we could get the k out of the coefficient on the RHS we could move it outside the summation. But I can't see any way to do that.
-Dan