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
    9
    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, 10:47 AM
  2. Replies: 1
    Last Post: September 5th 2010, 10:15 AM
  3. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 01:09 PM
  4. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 09:38 AM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum