Results 1 to 5 of 5

Thread: 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
    21,776
    Thanks
    2823
    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 $\displaystyle \binom{n+1}{2}+\binom{n}{2}=n^2$ or $\displaystyle \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,577
    Thanks
    790

    Re: Bijective Proof

    Bijective Proof-bijective.png

    The number of squares above (or below) a diagonal in a square of size n is $\displaystyle \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 $\displaystyle 1 \le i,j \le n$. There are $\displaystyle n^2$ of these.

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

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

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

    Comparing our results, we see $\displaystyle 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 $\displaystyle 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; Aug 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,546
    Thanks
    842

    Re: Bijective Proof

    a simple algebraic proof:

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

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

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

    $\displaystyle = \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: Mar 30th 2010, 09:49 PM
  3. bijective proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 12th 2009, 01:09 PM
  4. Bijective function proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: Apr 23rd 2009, 04:35 PM
  5. Bijective Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 2nd 2009, 12:30 PM

Search Tags


/mathhelpforum @mathhelpforum