proof by induction question involving power set

**rpatel** · January 21st 2010, 12:55 AM

Hi

My question is
Prove by induction that if A has n elements, then $P(A)$ has $2^{n}$ elements.

thanks

**Drexel28** · January 21st 2010, 05:23 AM

Originally Posted by rpatel

Hi

My question is
Prove by induction that if A has n elements, then $P(A)$ has $2^{n}$ elements.

thanks

Hint: Find a recurrence relation. Call $p(n)$ the number of things in a set with $n$ elements and then partition a set containing $n+1$ elements into two blocks. Those the contain $n+1$ and those that don't.

**novice** · January 21st 2010, 07:19 AM

Originally Posted by Drexel28

Hint: Find a recurrence relation. Call $p(n)$ the number of things in a set with $n$ elements and then partition a set containing $n+1$ elements into two blocks. Those the contain $n+1$ and those that don't.

Very clever!

**Dinkydoe** · January 21st 2010, 08:50 AM

For every $x\in P(n)$ we have 2 choices: Do we add $n+1\in x$ or not.

**rpatel** · January 21st 2010, 11:00 AM

how do i partition the set ?

**novice** · January 21st 2010, 11:30 AM

Originally Posted by Dinkydoe

For every $x\in P(n)$ we have 2 choices: Do we add $n+1\in x$ or not.

If we do it by induction, we have only $n$ number to consider, but Drexel suggested it by number of ways to partition, in which case the empty set $\emptyset$ must be added into consideration, which is why he said $n+1$ instead of $n$ .

If the empty set is not considered, we will end up getting $2^{n-1} - 1$ , instead of $2^n$ .

By induction, we need to name the set. Let $A$ be the set such that $x \in A$

By induction, we can begin with the base case, n=0, where $\emptyset$ is the only member, i.e. When $n= 0$ , $P(A_0)$ contains $2^n = 2^0 = 1$ members. The subscript denotes the number of elements in the set $A$ .

Next, assume it is true that the set $A$ containing $n$ members, written $A_n$ to have the Power set containing $2^n$ .

The prove $P(A_{n+1})$ contain $2^{n+1}$ members.

We know $P(A_n)$ contains $n$ number of elements. Since $x \in A$ , we need to introduce an element that is not in $A$ , say $y \notin A$ so that

$<br /> P(A_{n+1}) = P(A_n \cup \{y\})<br />$

The set $P(A_n \cup \{y\})$ will have additional members that look like this:

$\{\{\emptyset \} \cup \{y\}, \{1\} \cup \{y\}, \{2\} \cup \{y\}, ......\{......(n-2),(n-1),n\} \cup \{y\}\}$ which gives an additional $2^n$ members to the original set, $P(A)$ .

**novice** · January 21st 2010, 11:52 AM

Originally Posted by rpatel

how do i partition the set ?

If A = {a,b,c,d} and we want to partition it into 2 groups, it will look like {a|b,c,d} or {a,b|c,d}. To partition it into 3 groups, it will become {a|b|c,d} or {a,b|c|d} or {a|b,c|d} or {a,b|c|d}.

**novice** · January 21st 2010, 04:58 PM

Originally Posted by Drexel28

Hint: Find a recurrence relation. Call $p(n)$ the number of things in a set with $n$ elements and then partition a set containing $n+1$ elements into two blocks. Those the contain $n+1$ and those that don't.

I just cannot see how this can be considered proof by induction. It seems to me that by partitioning we get to it by binomial theorem. I cannot see where the $n+1$ goes.

The only way I can think off is as follows:

Let $A$ be a set of $n$ elements, then in the Power set $P(A)$ there are:

$\binom{n}{0}$ number of { $\emptyset$ }
$\binom{n}{1}$ number of singleton sets, {1}, {2}, {3}, ....{n}
$\binom{n}{2}$ number of doublets, {1,2}, {1,3}, {1,4}, ....{n}
$\binom{n}{3}$ number of triplets, {1,2,3}, {1,2,4}, {1,2,5}, ....{n}

.
.
.
$\binom{n}{n}$ number of { $A$ }

All together $|P(A_n)| =\Sigma_{i=0}^n \binom{n}{i}a^i b^{n-i}= 2^n$ , where $a = 1$ and $b=1$

I know for sure that my method is not by induction.
Drexel, I am think of a different thing?

**Drexel28** · January 21st 2010, 05:40 PM

Originally Posted by novice

I just cannot see how this can be considered proof by induction. It seems to me that by partitioning we get to it by binomial theorem. I cannot see where the $n+1$ goes.

I know for sure that my method is not by induction.
Drexel, I am think of a different thing?

Theorem: For a finite set $E$ with $\text{card }E=n$ we have that $\text{card }\wp\left(E\right)=2^n$

Proof: Let $p(n)$ be the number of subsets of $\left\{1,\cdots,n\right\}$ . Consider the set $\left\{1,\cdots,n,n+1\right\}=E'$ . Partition $E'$ into two cells $B_1,B_2$ where $B_1$ contains all subsets $S$ of $\left\{1,\cdots,n,n+1\right\}$ such that

$n+1\notin S$ and $B_2=E'-B_1$ . Evidently, we have that $\text{card }B_1$ is the number of subsets one can form from $\left\{1,\cdots,n\right\}$ which is $p(n)$ . We have two choices for the elements $S'$ , either $S'=\{n+1\}$

or it contains some element of $\{1,\cdots,n\}$ . Clearly, the latter case tells us that there is an element of $B_2$ for each non-empty subset in $B_1$ which is $p(n)-1$ . And, it clearly follows that the number

of elements of $B_2$ is the $p(n)-1$ with the addition of $\{n+1\}$ so that $\text{card }B_2=p(n)$ . Thus, $\text{card}\{1,\cdots,n,n+1\}=\text{card }B_1+\text{card }B_2=p(n)+p(n)=2p(n)$ . But,

$\text{card }\left\{1,\cdots,n,n+1\right\}=p(n+1)$ , so that $p(n+1)=2p(n)$ . This is a simple linear homogeneous recurrence relation with solution $p(n)=C\cdot 2^n$ for some constant. But, seeing that $p(0)$ is the

number of subsets of $\varnothing$ which is zero we see that $1=p(0)=C\cdot2^0=C$ from where it follows that $p(n)=2^n$ . The conclusion follows since any set of $n$ elements is, by definition, equipotent to

$\left\{1,\cdots,n\right\}$ . $\blacksquare$

Remark: The induction was implicitly used in solving the recurrence relation.

**novice** · January 21st 2010, 06:32 PM

Originally Posted by Drexel28

Theorem: For a finite set $E$ with $\text{card }E=n$ we have that $\text{card }\wp\left(E\right)=2^n$

Proof: Let $p(n)$ be the number of subsets of $\left\{1,\cdots,n\right\}$ . Consider the set $\left\{1,\cdots,n,n+1\right\}=E'$ . Partition $E'$ into two cells $B_1,B_2$ where $B_1$ contains all subsets $S$ of $\left\{1,\cdots,n,n+1\right\}$ such that

$n+1\notin S$ and $B_2=E'-B_1$ . Evidently, we have that $\text{card }B_1$ is the number of subsets one can form from $\left\{1,\cdots,n\right\}$ which is $p(n)$ . We have two choices for the elements $S'$ , either $S'=\{n+1\}$

or it contains some element of $\{1,\cdots,n\}$ . Clearly, the latter case tells us that there is an element of $B_2$ for each non-empty subset in $B_1$ which is $p(n)-1$ . And, it clearly follows that the number

of elements of $B_2$ is the $p(n)-1$ with the addition of $\{n+1\}$ so that $\text{card }B_2=p(n)$ . Thus, $\text{card}\{1,\cdots,n,n+1\}=\text{card }B_1+\text{card }B_2=p(n)+p(n)=2p(n)$ . But,

$\text{card }\left\{1,\cdots,n,n+1\right\}=p(n+1)$ , so that $p(n+1)=2p(n)$ . This is a simple linear homogeneous recurrence relation with solution $p(n)=C\cdot 2^n$ for some constant. But, seeing that $p(0)$ is the

number of subsets of $\varnothing$ which is zero we see that $1=p(0)=C\cdot2^0=C$ from where it follows that $p(n)=2^n$ . The conclusion follows since any set of $n$ elements is, by definition, equipotent to

$\left\{1,\cdots,n\right\}$ . $\blacksquare$

Remark: The induction was implicitly used in solving the recurrence relation.

Aha, I got it now after staring at it and pulling my hair.

You are a genius! Wow!

**Dinkydoe** · January 21st 2010, 07:24 PM

We don't necessary have to make things overcomplicated:
Let $A_n = \left\{1,\cdots ,n \right\}$

Step 1.

card $\mathcal{P}(A_0))= 2^0 = 1$ is satisfied.

step 2. Fix some $N > 0$ . Assume for all $n \leq N$ we have card( $\mathcal{P}(A_n)) = 2^n$ .

From $\mathcal{P}(A_n)$ we can construct $\mathcal{P}(A_{n+1})$ . Namely by doing the following:
Let $P = \emptyset$ .

Let $S \in\mathcal{P}(A_n)$ :

1. Add a copy of $S$ in $P$ .
2. Take another copy of $S$ and let $n+1\in S$ and add it to $P$ .

We don't have to sit here and discuss for hours that we constructed $P = \mathcal{P}(A_{N+1})$ .

Now evidently card $\mathcal{P}(A_{N+1}) = 2\cdot$ card $\mathcal{P}(A_N) = 2\cdot 2^N = 2^{N+1}$ by the induction hypothesis.

step 3. By induction follows from step 1+step 2 that for all $n\in \mathbb{N}$ we have card $\mathcal{P}(A_n) = 2^n$

**Drexel28** · January 21st 2010, 07:32 PM

Originally Posted by Dinkydoe

We don't necessary have to make things overcomplicated:
Let $A_n = \left\{1,\cdots ,n \right\}$

Step 1.

card $\mathcal{P}(A_0))= 2^0 = 1$ is satisfied.

step 2. Fix some $N > 0$ . Assume for all $n \leq N$ we have card( $\mathcal{P}(A_n)) = 2^n$ .

From $\mathcal{P}(A_n)$ we can construct $\mathcal{P}(A_{n+1})$ . Namely by doing the following:
Let $P = \emptyset$ .

Let $S \in\mathcal{P}(A_n)$ :

1. Add a copy of $S$ in $P$ .
2. Take another copy of $S$ and let $n+1\in S$ and add it to $P$ .

We don't have to sit here and discuss for hours that we constructed $P = \mathcal{P}(A_{N+1})$ .

Now evidently card $\mathcal{P}(A_{N+1}) = 2\cdot$ card $\mathcal{P}(A_N) = 2\cdot 2^N = 2^{N+1}$ by the induction hypothesis.

step 3. By induction follows from step 1+step 2 that for all $n\in \mathbb{N}$ we have card $\mathcal{P}(A_n) = 2^n$

Not to be a combative Carl, but what you did doesn't look any simpler than what I did. Also, mine seems to be more descriptive. Any comment?

**Dinkydoe** · January 21st 2010, 07:39 PM

Well I clearly hold to the induction-procedure ;p

Aside from that, I took some extra unnecessary steps and construct an extra Set P.

However from the induction-hypothesis and the observation that for every element of $\mathcal{P}(A_n)$ we can choose to add or not add an extra element N+1, the conclusion follows.

I think that's clearly more straightforward approach.

**Drexel28** · January 21st 2010, 07:41 PM

Originally Posted by Dinkydoe

Well I clearly hold to the induction-procedure ;p

Aside from that, I took some extra unnecessary steps and construct an extra Set P.

However from the induction-hypothesis and the observation that for ever element of $\mathcal{P}(A_n)$ we can choose to add or not add an extra element N+1, the conclusion follows.

I think that's clearly more straightforward approach.

I mean, really, the only difference between mine and yours is that you went into less detail. Which is probably a good thing!

**Dinkydoe** · January 21st 2010, 07:44 PM

I mean, really, the only difference between mine and yours is that you went into less detail. Which is probably a good thing!

Exactly! The questioner probably wants answers, no essays

Thread: proof by induction question involving power set

LinkBack

Thread Tools

Display

proof by induction question involving power set

Similar Math Help Forum Discussions

[SOLVED] strong induction problem involving power set

[SOLVED] Theorem involving delta function: proof by induction

Help involving induction proof

proof involving power sets, and intersection

Induction proof involving sums of consecutive powers

Search Tags