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
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.