(adsbygoogle = window.adsbygoogle || []).push({}); 1. The problem statement, all variables and given/known data

(a) Use induction to show that if n(A) = n then n(P(A)) = 2^n.

n(A) is the cardinality of set A.

P(A) is the power set of A.

2. Relevant equations

The answer is

We apply induction to prove the claim.

If n = 0 then A = null and in this case P(A) = {null}. Thus n(P(A)) = 1 = 2^0.

As induction hypothesis, suppose that if n(A) = n then n(P(A)) = 2^n. Let B = {a1, a2, · · · , an, an+1}. Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of

{a1, a2, · · · , an} with the element an+1 added to them. Hence, n(P(B)) =

2^n + 2^n = 2 · 2^n = 2^n+1.

3. The attempt at a solution

Can someone explain the step

"Then P(B) consists of all subsets of {a1, a2, · · · , an} together with all subsets of {a1, a2, · · · , an} with the element an+1 added to them. "

Why is this the case? Shouldn't P(B) just all the subsets {a1,a2,...,an,an+1)? So that's the power set of {a1,a2,...,an} plus something else, but what is that something else?

The answer seems to say that the something else isall subsets of {a1, a2, · · · , an} with the element an+1and that is equal to 2^n but why is that the case? How do we know that it is equal to 2^n?

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Homework Help: Prove Power Set equation by Induction

**Physics Forums | Science Articles, Homework Help, Discussion**