HW1 Discussion, MA453, Fall 2008, Prof. Walther

Problem Statement

Could somebody please state the problem

Using Binomial Theorem, $(a+b)^n=\binom{n}{0}a^n+ \binom n 1 a^{n-1} b+...+\binom{n}{n}b^n$ .

We have $\binom{n}{0}+ \binom{n}{1}+...+\binom{n}{n}=(1+1)^n=2^n$

Base case:
n=0: $$ 2^0=1 $$ Subsets with 0 elements: {∅}
n=1: $$ 2^1=2 $$ Subsets with 1 elements: {∅}, {1}

So we can assume a set S with n elements has $$ 2^n $$ subsets.

n+1: $$ 2^(n+1) = 2^1 + 2^n = 2*2^n = 2^(n+1) $$

-Jesse Straeter