Miss.Bossy did a fine job of outlining the general structure of an inductive proof.
I will try to give some more details.
Step 1: Prove the statement for n=1:
A set with 1 element has
subsets.
The two subsets are (1) the set with that one element and (2) the null set
.
Step 2: Assume the statement is true for n:
This means assume that a set with n elements has
subsets.
Step 3: Now prove that a set with n+1 elements has
subsets:
In doing this, you can use the assumption that a set with n elements has
subsets.
Consider a set with n+1 elements.
Take one element out of this set with n+1 elements.
By the assumption of step 2, the reduced set with n elements has
subsets.
When you put the n+1 element back in the set, you get
subsets.
This is true because each of the previous
subsets gives rise to 2 subsets:
-----a new subset containing the new element
-----an "old" subset not containing the new element. This subset was in the
subsets counted in step 2.
Simplify your
expression to get your final count of
subsets.
Many students have trouble at first with proof by induction because it is very different from more direct proof. But, believe it or not, some things are much easier to prove by induction.
Try to keep in mind the 3-part structure to guide you. It takes practice. Seeing a number of examples will help you create strategies for constructing inductive proofs.