• Jun 20th 2010, 11:56 AM
huntsty
Let S be a set with n elements. Show:

If an (n is subscript) equals the number of subsets of S then an+1 (n+1 is subscript) = 2an (n is subscript)

Use this to prove by induction that an (n is subscript) = 2^n
• Jun 20th 2010, 12:24 PM
Plato
Quote:

Originally Posted by huntsty
Let S be a set with n elements. Show:
If an (n is subscript) equals the number of subsets of S then an+1 (n+1 is subscript) = 2an (n is subscript)

What you want to show that if \$\displaystyle 2^n\$ is the number of subsets of \$\displaystyle \{1,2,3,\cdots,n\}\$;
then \$\displaystyle 2^{n+1}\$ is the number of subsets of \$\displaystyle \{1,2,3,\cdots,n,n+1\}\$.
Think \$\displaystyle \{1,2,3,\cdots,n,n+1\}=\{1,2,3,\cdots,n\}\cup\{n+1 \}\$.
Any subset of \$\displaystyle \{1,2,3,\cdots,n\}\$ is also a subset of \$\displaystyle \{1,2,3,\cdots,n+1\}\$.
Take anyone of those and add \$\displaystyle n+1\$ to it to get a different subset of \$\displaystyle \{1,2,3,\cdots,n+1\}\$.
• Jun 20th 2010, 12:53 PM
huntsty
thank you, very helpful for understanding. I just don't know how to symbolically show this. Will i need to introduce a new random variable in my proof?
• Jun 20th 2010, 01:03 PM
Plato
Quote:

Originally Posted by huntsty
thank you, very helpful for understanding. I just don't know how to symbolically show this. Will i need to introduce a new random variable in my proof?

It comes down to this \$\displaystyle 2^n+2^n=2^?\$
• Jun 21st 2010, 11:02 AM
HallsofIvy
If S contains n+ 1 members, choose one of them and call it "a". Removing that from S leaves you with set T that has n members and so, a(n) members.

Now note that every member of S either contains "a" or it doesn't. If it doesn't, it is one of the a(n) subsets of T. If it does, then it is one of the subsets of T with "a" added- there are still a(n) such subsets. Together there are a(n)+ a(n)= 2a(n) subsets of S.