Results 1 to 4 of 4

Math Help - Need help understanding a proof!

  1. #1
    Member
    Joined
    Jun 2013
    From
    Israel
    Posts
    158

    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!
    Attached Thumbnails Attached Thumbnails Need help understanding a proof!-question..png  
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769

    Re: Need help understanding a proof!

    Quote Originally Posted by davidciprut View Post
    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 View Post
    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 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,367
    Thanks
    1313

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2013
    From
    Saudi Arabia
    Posts
    440
    Thanks
    86

    Re: Need help understanding a proof!

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Need help understanding a proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 25th 2012, 08:48 PM
  2. Understanding Topology Proof
    Posted in the Differential Geometry Forum
    Replies: 7
    Last Post: July 19th 2011, 07:49 AM
  3. Help understanding proof
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: November 9th 2010, 10:58 AM
  4. Help Understanding a Proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: December 23rd 2009, 08:37 PM
  5. understanding continuety proof..
    Posted in the Calculus Forum
    Replies: 3
    Last Post: January 2nd 2009, 06:27 PM

Search Tags


/mathhelpforum @mathhelpforum