# Need help understanding a proof!

• Dec 7th 2013, 04:04 AM
davidciprut
Need help understanding a proof!
Hi everyone, can someone explain me this proof? I really didn't understand. I didn't understand the functions that he defined mostly. And if you have a better proof for this can you post it ? Thanks!
• Dec 7th 2013, 04:39 AM
emakarov
Re: Need help understanding a proof!
Quote:

Originally Posted by davidciprut
I need help understanding a proof written in my notebook.

Ask the one who wrote it in your notebook to explain it to you! :) Just kidding.

Quote:

Originally Posted by davidciprut
can someone explain me this proof? I really didn't understand.

OK, but do you understand the definitions, like $C_n^k$? The idea of the proof is to show that the number of subsets with k elements equals the number of subsets with n - k elements. To do this, the author defines two collections of subsets: one has all subsets with k elements, the other has all subsets with n - k elements. To show that these collections are equinumerous, the proof defines two functions φ and ψ from one collection to the other and claims that they are mutually inverse. That is, each element of the first collection corresponds to one and only one element of the second collection.

Quote:

Originally Posted by davidciprut
I didn't understand the functions that he defined mostly.

I am not sure what it means to understand a function. A definition is a definition: it says, take this, do this operation, call the result thus. There is nothing to understand. You may not understand the rationale behind the definition, but first you need to follow through the proof and see if it works out. You may find that it is a valid proof even if you don't have an intuitive grasp of it.
• Dec 7th 2013, 07:58 AM
HallsofIvy
Re: Need help understanding a proof!
The statement to be proved is that C(n, n-k)= C(n, k). I assume that "C(n, i)" is defined in your text but you don't give the definition here!
I think "C(n, i)" is the "binomial coefficient". In many texts, that is defined as $C(n, k)= \frac{n!}{i!(n-i)!}$. In that case, the proof would be just a straightforward computation. But it appears that, here, the proof of C(n, k) is "the number of subsets, of a set containing n elements, that contain k elements". To prove that C(n, n-k)= C(n, k), using that definition, observe that if subset B, of set A (containing n elements), contains k elements, then the complement of B contains the other n- k elements of A. That is, to every subset of A with k elements, there is associated one with n-k elements.

That's the point of the two functions. $\phi$ is the function that to each subset B assigns its complement and $\psi$ is the inverse function.
• Dec 7th 2013, 09:07 AM
MINOANMAN
Re: Need help understanding a proof!