Question

i know that Number of subsets of a set \(S\) of size n , is given by the binomial sum

> **\(\sum_{k=1} ^n \binom{n}{k}=2^n\)** , n=1,2,3,.. elements

how we could conclude of prove this formula ? how to prove that this gives the number of subsets . where did this formula come from ?

**PS:-** i know how to prove \(\sum_{k=0} ^n \binom{n}{k}=2^n\)

Answer 1

use induction

Answer 2

no no no -.-

Answer 3

and there are dozens of other proofs too, but i have worked this using induction recently... so...

Answer 4

hmm what i need is how to get this
http://prntscr.com/4j52yx

Answer 5

Okay, lets do an informal proof using counting argument

Answer 6

i know all proofs that shows \(\sum_{k=0} ^n \binom{n}{k}=2^n\)

i wanna know where did it come from

Answer 7

ok show me.

Answer 8

you want a proof for number of subsets ?

or the binomial identity : \(\sum_{k=0} ^n \binom{n}{k}=2^n\) ?

Answer 9

Try using counting arguments. If you "expand" the summation as a sum of binomial coefficients, hopefully it will make sense to justify each of those combinations. Then you just "contract" the sum of these binomial coefficients using the binomial theorem to get 2^n

Answer 10

i wanna prove number of subsets , like the number of subsets of a finite set.

Answer 11

seems no one get my question -.-
every one trying to teach me how binomial (1+1)^n goes to sum of (n,k)
which i already know.

Answer 12

If there are "n" elements in a set, you can form the following subsets:
Select one item at a time. There will be nC1 subsets.
Select two items at a time. There will be nC2 subsets.
....
Select 'n' items at a time. There will be nCn subsets.

Add them all.

Answer 13

Notice that you can either include a particular element in your subset or not - So how many choices do you have for each element ?

Answer 14

hmmm same idea aum

Answer 15

ok so its about choises ?
like how many sets i can get from n elements without repeating ?!
OH my , thats exactly what i was looking for xD

Answer 16

Thats not my question. Maybe lets work this with a general example.

Suppose your master set \(\large M\) contains \(n\) elements

Answer 17

Next, consider a subset \(\large A\)

Answer 18

Any element in in \(\large M\) has exactly \(\large 2\) choices :

1) either the element exists in subset \(A\)
2) or it doesn't exist in subset \(A\)

Answer 19

So total number of ways a subset can be formed = 2x2x...n times = 2^n

Answer 20

i see mm

Answer 21

that was quick

Answer 22

its an one liner

induction proof is more beautiful though

Answer 23

ok show me

Answer 24

I was going with the same idea as @aum which seemed fairly simple.

Answer 25

will do induction some other time

have u noticed that the previous counting argument is very much analogous to finding number of divisors of a number

Answer 26

i know it its cool i know hmmm i was freaked out to see order stuff of subgroup -.-

Answer 27

if \(\large n = p_1^{e_1} p_2^{e_2} \ldots p_r^{e_r} \)

number of divisors = \((e_1+1)(e_2+1)\cdots (e_r+1)\)

Answer 28

somehow its tricky to to see the exact connection, but you can see that both proofs are similar

Answer 29

what about the order ?

Answer 30

there is 500 page book i have to review this week lol
im only lost how to start hehehe

Answer 31

this link has induction proof
http://www.artofproblemsolving.com/Wiki/index.php/Power_set

Answer 32

ok cool , i know that too

Answer 33

Oh so you did not open the textbook till now is it

Answer 34

hmm haha clear , yes

Answer 35

its like i know everything , but know nothing
random knowllege controling my head but its like without direction somehow >.<
idk if im making any sense

Answer 36

not used to do it on my own.

Answer 37

+ my teacher dont reply to my emails xD

Answer 38

elderly advice : you should study from the start and stick to some timetable; if you study randomly, your grades also will be random :P

Answer 39

thanks for the spirits up lol

Answer 40

just saying lol one week=7days is good enough time to master anything, including wiles proof of fermat's last theorem ! good luck !!

Answer 41

>.<
u dnt know abstract algebra is fully

Answer 42

you took abstract before right ? why are u studying again ?

Answer 43

\[2^n=(1+1)^n\]
Apply the binomial theorem.

Answer 44

thank you all ^^