| (3 intermediate revisions by 2 users not shown) | |||
| 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>. | 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> | 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]] | ||
Latest revision as of 15:48, 22 October 2010
Contents
HW1, Chapter 0, Problem 21, MA453, Fall 2008, Prof. Walther
Problem Statement
Could somebody please state the problem
Discussion
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 $
Using Induction
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
