Results 1 to 4 of 4

Math Help - Induction

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    18

    Induction

    Use induction to prove that a finite set with n elements has 2^n subsets.
    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
    See here:

    http://www.cs.uiuc.edu/class/fa08/cs...es/lect_17.pdf

    Google your problem. It's found all over the place.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,607
    Thanks
    1574
    Awards
    1
    Quote Originally Posted by cj's mom View Post
    Use induction to prove that a finite set with n elements has 2^n subsets.
    The statement holds for n=1: \emptyset  \subseteq \left\{ 1 \right\}\;\& \;\left\{ 1 \right\} \subseteq \left\{ 1 \right\}.

    Now suppose that S = \left\{ {1,2, \cdots ,k} \right\} and S has 2^k subsets.
    Consider S^+=S \cup \left\{ {k + 1} \right\}. Each subset of S is also a subset of S^+ this is 2^k subsets. Unite each subset of S with \left\{k+1\right\} giving us 2^k subsets more subsets. So we have 2^k  + 2^k  = 2\left( {2^k } \right) = 2^{k + 1} subsets of S^+. That completes the induction.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2008
    From
    Scotland
    Posts
    901
    See above... then!
    Last edited by Mush; January 18th 2009 at 02:05 PM. Reason: Reiterated.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 12:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 05:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 04:10 PM

Search Tags


/mathhelpforum @mathhelpforum