Combinatorial proof

Apr 2017
165
6
New York
I have solved the second one ( C(2n,n) one).
I am still working on the first one.
 

skipjack

Forum Staff
Dec 2006
21,473
2,466
How do you prove the second one?
 
Apr 2017
165
6
New York
I will tell you if you show me the first one :)
 
Apr 2017
165
6
New York
by the way there isn't a subject titled "discrete math" so I had to post it under abstract algebra.
 
Last edited:
Apr 2017
165
6
New York
number two is proven like this:

right handside is the square of C(n.k). separate the factors. C(n,k) * C(n.k)
and from the combinational identity we know that C(n,k) can be rewritten as C(n, n-k)

now using the Theorem C(m+n, k) = Sigma...

OK leT me attach the solution that is faster.
I have attached two photos.
 

Attachments

SDK

Sep 2016
793
540
USA
For the first one you should notice that the left hand side looks an awful lot like a derivative. In particular, what happens if you differentiate
\[ (1 + x)^n = \sum_{k=0}^n {{n}\choose{k}} x^k\]
and evaluate it at $x = 1$?
 
  • Like
Reactions: 1 person
Apr 2017
165
6
New York
hm that looks interesting. did not thought of that. I should try.
Also the hint in the question is :

"Think about picking a club and its president."


what do you think?