Let A = {1, 2, 3,... k} where k > 0. How many subsets of A are there such that they all have?

Question

element 1 but not 2? Express your answer in terms of k. Give an informal proof supporting your answer.

Answer 1

n.b.: By definition ''empty set'' is subset of all sets

A = {1,2,3, ...,k}

Proof :

n =1

{1} => {empty set, 1} => 2 subsets

n=2

{1,2 } => {empty set, {1},{2},{1,2}} => 4 subsets

n=3

{1,2,3} => {empty set, {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}} => 8 subsets

{1,2,3,4} => 16 subsets


_
_
_

n=k

{1,2,3,...,k} with k>0

=> For a set A with k elements with have 2^n subsets.

Formula (*)=> p = 2^n with n > 0 and p => (number of
subsets)

Verification

n = 2 => p = 2^2 = 4 subsets (true)

with formula (*) we can extrapolate all numbers of subset for
a finite set.

example : if n = 100 => p = 2^100 subsets

Answer 2

Since we must put 1 in, and leave 2 out, there are no choices where these two elements are involved. Now, for each of 3, 4, ..., k (there are k - 2 of these) we have two choices: we can put the element into the subset or we can leave it out. There are
2^(k-2) ways to make these choices.