Results 1 to 5 of 5

Math Help - Bijective Proof

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    13

    Bijective Proof

    I have been given a problem to prove the following by a bijective proof. Im not even sure where to start on the bijection if any help can be given that would be great!!

    the identity is:

    (n choose 2) + ((n+1) choose 2) = n^2

    Sorry i dont know how to display the message so that it looks mathematicaly correct.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1

    Re: Bijective Proof

    Quote Originally Posted by myenemy View Post
    I have been given a problem to prove the following by a bijective proof. Im not even sure where to start on the bijection if any help can be given that would be great!!
    the identity is: (n choose 2) + ((n+1) choose 2) = n^2
    What is meant by bijective proof?

    It seems that you want \binom{n+1}{2}+\binom{n}{2}=n^2 or \frac{(n+1)!}{2!(n-1)!}+\frac{(n)!}{2!(n-2)!}=n^2
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Bijective Proof

    Bijective Proof-bijective.png

    The number of squares above (or below) a diagonal in a square of size n is \binom{n}{2}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1

    Re: Bijective Proof

    Here is a slightly different approach.

    Consider the number of pairs (i, j) where 1 \le i,j \le n. There are n^2 of these.

    Let's break the pairs into two sets: (1) those with i < j, and (2) those with i \ge j.

    For (1), there are \binom{n}{2} such pairs.

    For (2), i \ge j \iff j \le i \iff j < i+1 \iff j < k where k = j+1, so 2 \le k \le n+1.
    If j < k then there are no solutions with j  = n+1 or k = 1; so the number of solutions is unchanged if we allow 1 \le i \le n+1 and 1 \le k \le n+1. So there are \binom{n+1}{2} such pairs.

    Comparing our results, we see n^2 = \binom{n}{2} + \binom{n+1}{2}.

    [edit]I suppose I should add, since the problem statement asks for a bijective proof, that the bijection is between the set n^2 pairs (i,j) and the union of the sets given in (1) and (2). I am assuming that what is called a "bijective" proof is the same as what is often called a "combinatoric" proof. [/edit]
    Last edited by awkward; August 31st 2012 at 04:26 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,317
    Thanks
    697

    Re: Bijective Proof

    a simple algebraic proof:

    \binom{n}{2} + \binom{n+1}{2}

    =\frac{n!}{2!(n-2)!} + \frac{(n+1)!}{2!(n-1)!}

    = \frac{(n-1)n}{2} + \frac{n(n+1)}{2}

    = \frac{n^2 - n}{2} + \frac{n^2 + n}{2} = \frac{2n^2}{2} = n^2
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 27th 2010, 11:11 PM
  2. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 30th 2010, 09:49 PM
  3. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 12th 2009, 01:09 PM
  4. Bijective function proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 23rd 2009, 04:35 PM
  5. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 2nd 2009, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum