Results 1 to 2 of 2

Math Help - help...inductive proof???

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    8

    Question help...inductive proof???

    can someone help me how to prove this...?

    Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2. [hint: Let x be any object of A and B=A-{x}. Then a 2-subset of A is either a 2-subset of B or a 1-subset of B. Count the number of subsets in each case.}

    -Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by memb3rme View Post
    can someone help me how to prove this...?

    Prove by induction that the number of 2-subsets of an n-set A equals n(n-1)/2. [hint: Let x be any object of A and B=A-{x}. Then a 2-subset of A is either a 2-subset of B or a 1-subset of B. Count the number of subsets in each case.}

    -Thanks
    The basic cases are trivial. Let \{a_1,...,a_n,a_{n+1}\}. Now the 2-subsets of this set are those that contain a_i,a_j where 1\leq i,j\leq n and there are n(n-1)/2 such sub-sets. Also any set involving a_{n+1} and anything else is another 2-subset and there are \{ a_1,a_{n+1}\}, ... \{a_n,a_{n+1}\} in total n such sub-sets. In total, we have n+n(n-1)/2 = n(n+1)/2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 3rd 2011, 11:47 AM
  2. Replies: 1
    Last Post: September 5th 2010, 11:15 AM
  3. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 02:09 PM
  4. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 10:38 AM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 07:24 PM

Search Tags


/mathhelpforum @mathhelpforum