Results 1 to 5 of 5

Math Help - Clueless on this proof, please help!!!

  1. #1
    Newbie
    Joined
    Jun 2010
    Posts
    2

    Clueless on this proof, please help!!!

    Let S be a set with n elements. Show:

    If an (n is subscript) equals the number of subsets of S then an+1 (n+1 is subscript) = 2an (n is subscript)

    Use this to prove by induction that an (n is subscript) = 2^n
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by huntsty View Post
    Let S be a set with n elements. Show:
    If an (n is subscript) equals the number of subsets of S then an+1 (n+1 is subscript) = 2an (n is subscript)
    What you want to show that if 2^n is the number of subsets of \{1,2,3,\cdots,n\};
    then 2^{n+1} is the number of subsets of \{1,2,3,\cdots,n,n+1\}.
    Think \{1,2,3,\cdots,n,n+1\}=\{1,2,3,\cdots,n\}\cup\{n+1  \}.
    Any subset of \{1,2,3,\cdots,n\} is also a subset of \{1,2,3,\cdots,n+1\}.
    Take anyone of those and add n+1 to it to get a different subset of \{1,2,3,\cdots,n+1\}.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2010
    Posts
    2
    thank you, very helpful for understanding. I just don't know how to symbolically show this. Will i need to introduce a new random variable in my proof?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by huntsty View Post
    thank you, very helpful for understanding. I just don't know how to symbolically show this. Will i need to introduce a new random variable in my proof?
    It comes down to this 2^n+2^n=2^?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,385
    Thanks
    1320
    If S contains n+ 1 members, choose one of them and call it "a". Removing that from S leaves you with set T that has n members and so, a(n) members.

    Now note that every member of S either contains "a" or it doesn't. If it doesn't, it is one of the a(n) subsets of T. If it does, then it is one of the subsets of T with "a" added- there are still a(n) such subsets. Together there are a(n)+ a(n)= 2a(n) subsets of S.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Absolutely clueless...
    Posted in the Algebra Forum
    Replies: 13
    Last Post: January 20th 2011, 06:12 AM
  2. Optimizations... Clueless
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 9th 2010, 05:04 PM
  3. Clueless
    Posted in the Algebra Forum
    Replies: 3
    Last Post: November 24th 2009, 08:20 AM
  4. Trig Review - Clueless
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: August 5th 2008, 07:58 PM
  5. 3x3 eigenvectors. Clueless.
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: April 6th 2008, 08:45 AM

Search Tags


/mathhelpforum @mathhelpforum