What is the proof that given a set of n elements there are 2n possible subsets (including the empty-set and the original set).
Answer
Suppose you want to choose a subset. For each element, you have two choices: either you put it in your subset, or you don’t; and these choices are all independent.
Remark: this works also for the empty set. An empty set has exactly one subset, namely the empty set. And the fact that 20=1 reflects the fact that there is only one way to pick no elements at all!
Attribution
Source : Link , Question Author : Celeritas , Answer Author : einpoklum
