Results 1 to 3 of 3

Math Help - Induction proof

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    6

    Induction proof

    Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    Let me illustrate in a lazy way.

    What we are being asked to do is choose 2 out of n. C(n,2).

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

    As you can see, everything cancels in the numerator and denominator except

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

    Check it, how many 2 subsets can be made from 10. C(10,2)=45

    \frac{10*9}{2}=45

    Now, we want to show an induction step.

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

    \frac{(n+1)(n)(n-1)(n-2)(n-3)......}{2(n-1)(n-2)(n-3).....}

    See what cancels this time?. Everything but \frac{n(n+1)}{2}

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

    And it is shown.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member JaneBennet's Avatar
    Joined
    Dec 2007
    Posts
    293
    Sorry Galactus, but I don’t think the question is asking us to assume any combinatorial formula at all. Here’s a more direct way.

    First, check that the statement is true for n=0. Obviously the empty set can’t have any subset with 2 elements and \frac{0(0-1)}{2}=0 so that’s fine. (To be on the safe side, we might also check the case n=1, possibly even n=2, but I’m sure the inductive method below works by just assuming n\geq0.)

    Now assume the statement is true for any set with n elements ( n\geq0). Consider a set A with n+1 elements and pick any element a\in A. (A contains at least 1 element.) Then A\backslash\{a\} contains n elements. The number of 2-element subsets of A not containing a is just the number of 2-element subsets of A\backslash\{a\}, which by the inductive hypothesis is \frac{n(n-1)}{2}. The number of 2-element subsets of A which do contain a is n (i.e. a plus any of the other n elements of A). So:

    no. of 2-element subsets of A = no. of 2-element subsets of A not containing a + no. of 2-element subsets of A containing a

    \color{white}.\hspace{45mm}. =\ \frac{n(n-1)}{2}\quad+\quad n

    which you should find is equal to \frac{(n+1)((n+1)-1)}{2}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum