• Home
• Foundations
Thomas A. Alspaugh
Mathematical Induction

Mathematical induction is a method of proof of propositions about a sequence of integers involving

• a basis step, in which a proposition P is proved about some specific integer, and
• an induction step, in which it is proved that if P is true for an integer n, then P is also true for the next integer in the sequence (usually n+1, but sometimes it's n+2 or 2n or something similar).

The integer in the basis step is the smallest one for which you are trying to prove P; often it's 1 or 0. In that case, if you (i) prove the basis step, and (ii) prove the inductive step, then you have proved the proposition P(j) for all integers 1 and greater (or 0 and greater if 0 was the basis case).

A proof by mathematical induction is convincing because you have in essence produced a recipe for constructing a proof of P for any integer in the range.

## Sum of consecutive positive integers

Proof that the sum of the consecutive positive integers 1 through n is n(n+1)/2.

We'll make 1 the basis case since the sequences begin with 1, and use ++ to define next integer.

Basis step:

1. The sum of the consecutive positive integers 1 through 1 is 1.
2. 1(1+1)/2 = 1.
3. So the sum of the consecutive positive integers 1 through n, for n=1, is n(n+1)/2.

Inductive step:

1. Assume that for some positive n, the sum of the consecutive positive integers 1 through k−1 is (k−1)(k)/2.
2. Then the sum of 1 through k is
(k−1)(k)/2 + k
= (k/2 − 1/2)(k) + k
= (k/2 − 1/2 + 1)(k)
= (k/2 + 1/2)(k)
= (k+1)(k)/2
= (k)(k+1)/2
3. So the sum of the consecutive positive integers 1 through n, under that assumption for n−1, is n(n+1)/2.

Now we can use the basis and inductive steps in a recipe to construct a proof for any positive integer j, thus:

1. Basis step proving P(1)
2. Induction step proving if P(1) then P(2)
3. Induction step proving if P(2) then P(3)
4. Induction step proving if P(j-1) then P(j)

Because we have shown how t construct a proof for any positive integer j, we have proved the proposition for all positive integers.

Proof of P ≡ The sum of the first n positive odd integers is n2.

Basis step: Prove P(1).

Inductive step: Prove that if k−2 is odd and P(k-2), then P(n).

Proof of P ≡ |2S| = 2|S| for finite set S.

Basis step: Prove P(∅).

Inductive step: Prove that if P(S) for a finite set of size k-1, then P(S') where S' is S plus one additional element.