# Combinatorial proof

#### Leonardox

Hi guys any idea how I can give combinatorial proof to the given identities?

#### Attachments

• 14.4 KB Views: 3
• 17.1 KB Views: 1

#### Leonardox

I have solved the second one ( C(2n,n) one).
I am still working on the first one.

#### skipjack

Forum Staff
How do you prove the second one?

#### Leonardox

I will tell you if you show me the first one

#### Leonardox

by the way there isn't a subject titled "discrete math" so I had to post it under abstract algebra.

Last edited:

#### Leonardox

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

• 19.9 KB Views: 2
• 22.1 KB Views: 2

#### SDK

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$?

1 person

#### Leonardox

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?