# Thread: Need help understanding a proof!

1. ## 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!

2. ## Re: Need help understanding a proof!

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.

Originally Posted by davidciprut
can someone explain me this proof? I really didn't understand.
OK, but do you understand the definitions, like $\displaystyle 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.

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.

3. ## 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 $\displaystyle 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. $\displaystyle \phi$ is the function that to each subset B assigns its complement and $\displaystyle \psi$ is the inverse function.