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:
- The sum of the consecutive positive integers 1 through 1 is 1.
- 1(1+1)/2 = 1.
- So the sum of the consecutive positive integers 1 through n, for n=1, is n(n+1)/2.
Inductive step:
- Assume that for some positive n, the sum of the consecutive positive integers 1 through k−1 is (k−1)(k)/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 - 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:
- Basis step proving P(1)
- Induction step proving if P(1) then P(2)
- Induction step proving if P(2) then P(3)
- …
- 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.
- thomas · alspaugh @ acm · org
-
-
Attribution