Proof by induction: Let P(n) be the proposition that a set with
n elements has 2^n subsets.
Basis step: P(0) is true, a set with zero elements,
namely the empty set, has exactly 2^0 = 1 subset.
Induction step: Assume P(k) is true for an arbitrary k. We need to show that P(k+1) is true.
To show this, let S has k+1 elements. Then S = {S'}U{w}, where w is one of elements of S and S' = S - {w}. The subsets of S can be obtained in the following way: for each subset T of S', there are exactly two subsets, namely T and TU{w}. These constitutes all the subsets of S, and are all distinct. Since there are 2^k subset of S', there are 2^k + 2^k = 2^(k+1) subsets of S. This finishes the induction argument.
Because we have completed the basis and inductive steps of mathematical induction, we conclude that P(n) is true.
Proof by (strong) induction:
Let P(n) be the proposition that n can be written as the product
of primes.
Basis step: P(2) is true, since 2 can be written as the
product of one prime, itself.
Induction step: Assume P(j) is true for all j <= k. We need to show that P(k+1) is true.
There are two cases: (a) k+1 is prime. In this case, we immediately
conclude that P(k+1) is true.
(b) k+1 is composite. In this case, k+1 = a*b and 2 <= a, b < k+1.
By the inductive hypothesis, both a and b can be written
as the product of primes. Thus we conclude that k+1 is a product
of primes.
Because we have completed the basis and inductive steps of mathematical induction, we conclude that P(n) is true for all n >= 2.
In addition, we can prove that the product is unique (except for order)
Suppose n = p1*p2*...*pk = q1*q2*...*qr, where p's and q's are primes.
Since p1 divides q1*q2*...*qr equals to one of q's, we rearrange
the q's so that p1 = q1. Then
p2*...*pk = q2*...*qr
By the same arguments, we can rearrange the remaining q's so that p2 = q2, and
so on. Thus n can be expressed uniquely as a product of prpimes (except for order).
Proof by (strong) induction:
Let P(n) be the proposition that postage of n (>= 12)
can be formed using 4-cent and 5-cent stamps.
Basis step: By straight examination, we conclude
P(12), P(13), P(14) and P(15) are true.
Induction step:
Assume that P(j) is true for 12 <= j <= k , where k is an integer with k >=15.
We need to show P(k+1) is true
Note that k+1 = k-3 + 4 and k-3 >= 12. Using the inductive hypothesis,
P(k-3) is true (namely, the postage of k-3 cents can be formed using 4-cent
and 5-cent stamps). Therefore, to form postage of k+1 cents, we need only
add another 4-cent stamp to the stamps we used to form postage of k-3 cents.
This completes the inductive step.
Because we have completed the basis and inductive steps of mathematical induction, we conclude that P(n) is true for all n >= 12.