MAT 1348 Study Guide - Final Guide: Mathematical Induction
17 May 2020
School
Department
Course
Professor
Lecture 21
Principle of Mathematical Induction
The Principle of Mathematical Induction (PMI) is a very strong tool
for proving propositions about integers.
Informally, the idea is to first show that the proposition is true for
the smallest integer for which the proposition is claimed to be true.
Once this is accomplished, we show that if the proposition is true for
some admissible integer then it is also true for the next admissible inte-
ger. These steps together give us a proof that the proposition is true for
any integer (for which it is defined). A more precise description follows.
Let P(n) be a proposition about integers. Let n0be the smallest
integer for which the proposition is defined.
PMI: If (1) P(n0) is T (true), and
(2) P(k)→P(k+ 1) is T for all k≥n0,
then P(n) is T for all n≥n0.
How to do/write a proof by induction:
(i) Clearly state P(n).
(ii) Basis of induction (BI): Choose an appropriate n0and prove
that P(n0) is true.
(iii) Induction Step (IS): Prove that P(k)→P(k+ 1) is True for
all k≥n0.
- Assume that P(k) is T for some k≥n0(this is the induction
hypothesis (IH)).
- Show that P(k+ 1) is T follows.
(iv) Conclusion: By PMI, since P(n0) is T and P(k)→P(k+ 1)
is T for k≥n0, it follows that P(n) is T for all n≥n0.
1
Document Summary
The principle of mathematical induction (pmi) is a very strong tool for proving propositions about integers. Informally, the idea is to rst show that the proposition is true for the smallest integer for which the proposition is claimed to be true. Once this is accomplished, we show that if the proposition is true for some admissible integer then it is also true for the next admissible inte- ger. These steps together give us a proof that the proposition is true for any integer (for which it is de ned). Let p (n) be a proposition about integers. Let n0 be the smallest integer for which the proposition is de ned. If (1) p (n0) is t (true), and (2) p (k) p (k + 1) is t for all k n0, then p (n) is t for all n n0. Assume that p (k) is t for some k n0 (this is the induction hypothesis (ih)).
