Power sets question

perusal

New member
Joined
Jan 7, 2019
Messages
48
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?
 
Yes, we can state:

[MATH]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[/MATH]
 
Yes, we can state:

[MATH]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[/MATH]


Thanks for your help.

How do we get from

[MATH]\sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)[/MATH]
to

[MATH](1+1)^n[/MATH]
 
How do we get from [MATH]\sum_{k=0}^n\left({n \choose k}1^{n-k}\cdot1^{k}\right)[/MATH]to [MATH](1+1)^n[/MATH]
You need to know the basic binomial expansion formula:
(x+y)n=k=0n(nk)xnkyk=xn+nxn1y+nxyn1+yn\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 x=1 & y=1\displaystyle x=1~\&~y=1 we have (1+1)n=2n\displaystyle (1+1)^n=2^n
Thus (2)n=k=0n(nk)\displaystyle {(2)^n} = \sum\limits_{k = 0}^n {\binom{n}{k}}
All you need to know now (nk)=n!k!(nk)!\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!} from n\displaystyle n choose k\displaystyle k, a subset of size k\displaystyle k in a set of size n\displaystyle n.
 
Top