Latest revision as of 16:48, 22 October 2010

HW1, Chapter 0, Problem 21, MA453, Fall 2008, Prof. Walther

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

@@ Line 1: / Line 1: @@
+=[[HW1_MA453Fall2008walther|HW1]], Chapter 0, Problem 21, [[MA453]], Fall 2008, [[user:walther|Prof. Walther]]=
+==Problem Statement==
+''Could somebody please state the problem''
+----
+==Discussion==
 Using Binomial Theorem, <math>(a+b)^n=\binom{n}{0}a^n+ \binom n 1 a^{n-1} b+...+\binom{n}{n}b^n</math>.
 We have <math>\binom{n}{0}+ \binom{n}{1}+...+\binom{n}{n}=(1+1)^n=2^n</math>
+----
+== Using Induction ==
+'''Base case:''' <br>
+n=0: <math>2^0=1</math> Subsets with 0 elements: {∅} <br>
+n=1: <math>2^1=2</math> Subsets with 1 elements: {∅}, {1}
+So we can assume a set ''S'' with ''n'' elements has <math>2^n</math> subsets.
+n+1: <math>2^(n+1) = 2^1 + 2^n = 2*2^n = 2^(n+1)</math>
+-Jesse Straeter
+----
+[[HW1_MA453Fall2008walther|Back to HW1]]
+[[Main_Page_MA453Fall2008walther|Back to MA453 Fall 2008 Prof. Walther]]