# Prove by induction: For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $2^N$ subsets. [duplicate]

For all N = 0, 1, 2, 3, ..: every finite set with N elements has exactly $2^N$ subsets.

How do I prove this by induction?

-
I missed that, sorry, @Git Gud. –  amWhy Apr 3 '13 at 21:49
@amWhy No problem. –  Git Gud Apr 3 '13 at 21:50

## marked as duplicate by Git Gud, Davide Giraudo, Américo Tavares, Amzoti, Dominic MichaelisApr 3 '13 at 22:30

Of course the empty set has $0$ elements and $1 = 2^0$ subsets.

Suppose you know the result for every set with $N-1$ elements. Let $A$ be a set with $n > 0$ elements. Fix an element $a_0 \in A$. Then a subset $C$ of $A$ is one of two kinds:

1. If $a_0 \in C$, then $C = \{ a_0 \} \cup B$, where $B$ is a subset of $A \setminus \{ a_0 \}$, so by induction there are $2^{N-1}$ subsets here, or
2. $a_0 \notin C$, and then $C \subseteq A \setminus \{ a_0 \}$, and here there are also $2^{N-1}$ subsets here.

The total is $2^{N-1} + 2^{N-1} = 2^{N}$.

-

You check it for $N=0$ to establish the induction base.

Now, for the induction step, assume the claim holds for $N=k$, and let $S$ be a set with $k+1$ elements. Pick an element $a\in S$ and fix it for the rest of the proof. Now, any subset $B\subseteq S$ either contains $s$ or it does not. Consider these two cases separately. How many subsets $B\subseteq S$ are there that do not contain $b$? Well, such a subset is simply a subset of $S-\{a\}$, and so you can use the induction hypothesis to answer that. How many subsets $B\subseteq S$ are there that do contain $a$? Well, such a subset $B$ is completely and uniquely determined by $B-\{a\}$, which is just an arbitrary subset of $S-\{a\}$, so the induction hypothesis again tells you how many such subsets you have. Combine the two result to obtain a proof of the induction step, and thus the proof by induction is complete.

-

Hint. Verify for $N=0$, assume true for $N=n$ and prove for $N=n+1$, using the fact you know it for $n$ already.

-

Let the statement be denoted by P(N) Case N=0. We have to prove P(0):set with zero elements has 2^0 (=1) subsets. Clearly a set with no elements is $\emptyset$ (null set) there fore has only $\emptyset$ as its subset.

Thus P(0) is true.

Case N=1. We have to prove P(1):set with one element has 2^1 (=2) subsets.

Clearly a set with 1 element has only 2 subsets,that and null set. Thus P(1) is true.

Now suppose P(x) is true where x $\varepsilon$ N. ie a set having x no. of elements has 2^x subsets.

we have to prove that P(x+1) is true when ever P(x) is true. P(x+1) : A set having x+1 elements has 2^(x+1) subsets. In this set we have n1,n2....nx and then nx+1 newly added. apart from the subsets that can be formed with n1,n2...nx. we can form subsets by choosing from any number among n1,n2...nx. ie.xC0+xC1+.... xCx = 2^x (xC0 for a set with nx+1 alone). Now trying to account for total number of subsets it becomes. 2^x+2^x = 2*2^x = 2^(x+1)

Thus by principle of induction P(x) is true for all x=0,1,2.

-
To format mathematics use tex code between dollar signs. E.g., $\emptyset$, the empty set, is formatted by writing \emptyset between dollar signs. –  Ittay Weiss Apr 3 '13 at 22:02
Thanks...Please upvote if u think answer is correct. –  Sreekanth Karumanaghat Apr 3 '13 at 22:07
you might also want to correctly format the rest of your answer. The answer is basically correct, but you should adhere to the standards of typesetting your posts with care. –  Ittay Weiss Apr 3 '13 at 22:09
Hint: If $N=\{a_1,\ldots,a_n\}$, then all subsets of $N$ can be obtained from subsets of $\{a_1,\ldots,a_{n-1}\},$ say $A$, by considering $A$ or $A\cup\{a_n\}$.