Power sets question

perusal

New member
Joined
Jan 7, 2019
Messages
9
Can someone explain to me why P({1,2,3}) is equal to 2^3

I understand how 8 is arrived at. {empty set, {1},{2},{3},{2,3},{1,2},{1,3},{1,2,3}}

What I don't understand is why it how this relates to 2^3

Has it got something to do with the binomial theorem?
 

MarkFL

Super Moderator
Staff member
Joined
Nov 24, 2012
Messages
1,819
Yes, we can state:

\(\displaystyle P_n=\sum_{k=0}^n\left({n \choose k}\right)=\sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)=(1+1)^n=2^n\)
 

HallsofIvy

Elite Member
Joined
Jan 27, 2012
Messages
5,042
It relates to the fact that 2^3 is equal to 8!
 

perusal

New member
Joined
Jan 7, 2019
Messages
9
Yes, we can state:

\(\displaystyle P_n=\sum_{k=0}^n\left({n \choose k}\right)=\sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)=(1+1)^n=2^n\)

Thanks for your help.

How do we get from

\(\displaystyle \sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)\)

to

\(\displaystyle (1+1)^n\)
 

MarkFL

Super Moderator
Staff member
Joined
Nov 24, 2012
Messages
1,819
Thanks for your help.

How do we get from

\(\displaystyle \sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)\)

to

\(\displaystyle (1+1)^n\)
Via the binomial theorem. :)
 

Dr.Peterson

Elite Member
Joined
Nov 12, 2017
Messages
4,125
Think about how you expand (a + b)^n by the binomial theorem. Then replace a and b with 1.
 

pka

Elite Member
Joined
Jan 29, 2005
Messages
8,319
How do we get from \(\displaystyle \sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)\)
to \(\displaystyle (1+1)^n\)
You need to know the basic binomial expansion formula:
\(\displaystyle {(x + y)^n} = \sum\limits_{k = 0}^n {\binom{n}{k}{x^{n - k}}{y^k}} = {x^n} + n{x^{n - 1}}y + \cdots nx{y^{n - 1}} + {y^n}\)
Now if \(\displaystyle x=1~\&~y=1\) we have \(\displaystyle (1+1)^n=2^n\)
Thus \(\displaystyle {(2)^n} = \sum\limits_{k = 0}^n {\binom{n}{k}}\)
All you need to know now \(\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}\) from \(\displaystyle n\) choose \(\displaystyle k\), a subset of size \(\displaystyle k\) in a set of size \(\displaystyle n\).
 

perusal

New member
Joined
Jan 7, 2019
Messages
9
Thanks for all the help. I understand now
 
Top