Mathematical induction is a method of proof of propositions about a sequence of integers involving
the next integerin 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.
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:
Inductive step:
Now we can use the basis and inductive steps in a recipe to construct a proof for any positive integer j, thus:
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 n^{2}
.
Basis step: Prove P(1).
Inductive step: Prove that if k−2 is odd and P(k-2), then P(n).
Proof of P ≡ |2^{S}| = 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.