An Introduction to Proof via Inquiry-Based Learning

Let’s take a look at potential proofs.

“Proof” of (a). If \(n=1\text{,}\) then \(1=\frac{1(1+1)}{2}\text{.}\) If \(n=2\text{,}\) then \(1+2=3=\frac{2(2+1)}{2}\text{.}\) If \(n=3\text{,}\) then \(1+2+3=6=\frac{3(3+1)}{2}\text{,}\) and so on.

“Proof” of (b). If \(n=1\text{,}\) then \(n^{2}+n+41=43\text{,}\) which is prime. If \(n=2\text{,}\) then \(n^{2}+n+41=47\text{,}\) which is prime. If \(n=3\text{,}\) then \(n^{2}+n+41=53\text{,}\) which is prime, and so on.

Are these actual proofs? No! In fact, the second claim is not even true. If \(n=41\text{,}\) then \(n^{2}+n+41=41^{2}+41+41=41(41+1+1)\text{,}\) which is not prime since it has 41 as a factor. It turns out that the first claim is true, but what we wrote cannot be a proof since the same type of reasoning when applied to the second claim seems to prove something that is not actually true. We need a rigorous way of capturing “and so on” and a way to verify whether it really is “and so on.”

Recall that an axiom is a basic mathematical assumption. The following axiom is one of the Peano Axioms, which is a collection of axioms for the natural numbers introduced in the 19th century by Italian mathematician Giuseppe Peano

¹

en.wikipedia.org/wiki/Giuseppe_Peano

(1858–1932).

We can think of the set \(S\) as a ladder, where the first hypothesis as saying that we have a first rung of a ladder. The second hypothesis says that if we are on any arbitrary rung of the ladder, then we can always get to the next rung. Taken together, this says that we can get from the first rung to the second, from the second to the third, and in general, from any \(k\)th rung to the \((k+1)\)st rung, so that our ladder is actually \(\mathbb{N}\text{.}\) Do you agree that the Axiom of Induction is a pretty reasonable assumption?

At the end of Section 3.2, we briefly discussed ZFC, which is the standard choice for axiomatic set theory. It turns out that one can prove the Axiom of Induction as a theorem in ZFC. However, that will not be the approach we take. Instead, we are assuming the Axiom of Induction is true. Using this axiom, we can prove the following theorem, known as the Principle of Mathematical Induction. One approach to proving this theorem is to let \(S=\{k\in \mathbb{N}\mid P(k) \text{ is true } \}\) and use the Axiom of Induction. The set \(S\) is sometimes called the truth set. Your job is to show that the truth set is all of \(\mathbb{N}\text{.}\)

The Principle of Mathematical Induction provides us with a process for proving statements of the form: “For all \(n\in\mathbb{N}\text{,}\) \(P(n)\text{,}\)” where \(P(n)\) is some predicate involving \(n\text{.}\) Hypothesis (i) above is called the base step (or base case) while (ii) is called the inductive step.

You should not confuse mathematical induction with inductive reasoning associated with the natural sciences. Inductive reasoning is a scientific method whereby one induces general principles from observations. On the other hand, mathematical induction is a deductive form of reasoning used to establish the validity of a proposition.

Prove the next few theorems using induction. The first result may look familiar from calculus. Recall that \(\displaystyle \sum_{i=1}^{n}i=1+2+3+\cdots +n\text{,}\) by definition.