## anonymous one year ago I need help to prove that $$\binom{n}{0}^2 + \binom{n}{1}^2 + \cdots + \binom{n}{n}^2 = \binom{2n}{n}.$$ using committee forming...

1. ganeshie8

suppose there are $$n$$ men and $$n$$ women and you want to choose a committee consisting of $$n$$ people

2. anonymous

thats 2n choose n

3. ganeshie8

Yes, lets count it in an alternative way

4. ganeshie8

how many committees will be there with out women ?

5. anonymous

*

6. anonymous

1

7. ganeshie8

Yes, how many committees will be there with exactly 1 women ?

8. anonymous

n choose n-1

9. ganeshie8

try again

10. anonymous

n choose n-1 multiplied by n?

11. ganeshie8

you can choose $$1$$ women from the group of $$n$$ women in $$\binom{n}{1}$$ ways after that, the remaining $$n-1$$ men can be chosen from the group of $$n$$ men in $$\binom{n}{n-1}$$ ways so total $$n$$ member committees with exactly $$1$$ women is $$\binom{n}{1}*\binom{n}{n-1}$$

12. ganeshie8

does that make sense

13. anonymous

yes, i get it

14. anonymous

now would i find the number of ways to make a committee with two women?

15. ganeshie8

yes find it, after that you will see the pattern

16. anonymous

alright, ill get back to you with the results :D

17. ganeshie8

take your time, we're almost done!

18. anonymous

hang on... n choose k and n choose (n-k) give the same result

19. anonymous

so the total possible combinations is just sums of the squares....

20. ganeshie8

Yep!

21. anonymous

but how do i equate it to 2n choose n?

22. anonymous

oh wait nevermind

23. anonymous

i get it

24. ganeshie8

good :) id like to see the complete proof if you don't mind

25. anonymous

sure :D

26. ganeshie8

take a screenshot and attach if psble

27. anonymous

i need to go eat dinner, i'll send it to you in about an hour, is that ok?

28. ganeshie8

take ur time

29. anonymous

i also need to prove the same thing using the "block walking" method... but i dont know how. Do you think you can try to help me with this too? please?

30. ganeshie8

sure that is also an interesting way to count first, may i see the previous proof...

31. anonymous

yes im just typing it up now

32. anonymous

sorry the codeisnt working...

33. ganeshie8

make this correction : $$k\le n$$

34. ganeshie8

other than that, the proof looks good!

35. anonymous

ok thanks!

36. anonymous

can you help me with the second part please?

37. anonymous

hello? are you still here @ganeshie8

38. ganeshie8

Hey!

39. anonymous

40. ganeshie8

Consider a $$n\times n$$grid |dw:1440165928386:dw|

41. anonymous

right

42. anonymous

number of paths from bottom left to top right = $$\binom{2n}{n}$$ |dw:1440168478785:dw|

43. anonymous

suppose your friend's home is located at $$(k,~n-k)$$, where $$k\in \left\{0,1,2,\ldots ,n \right\}$$. then number of paths through $$(k,n-k)$$ is given by $$\binom{n}{k}*\binom{n}{n-k} = \binom{n}{k}^2$$ ..... https://proofwiki.org/wiki/Sum_of_Squares_of_Binomial_Coefficients