Why is mathematical induction a valid proof technique?

Question

Context: I'm studying for my discrete mathematics exam and I keep running into this question that I've failed to solve. The question is as follows.

---

Problem: The main form for normal induction over natural numbers $n$ takes the following form:

1. $P(1)$ is true, and
2. for every $n, P(n-1)\to P(n).\qquad\qquad\qquad\text{[Sometimes written as $P(n)\to P(n+1)$]}$

If both 1 and 2 are true, then $P(n)$ is true for every $n$.

The question is to prove the correctness of the form above.

---

My work: My idea was to make a boolean statement and if it's a tautology in a true false table. That means the statement is always correct.

I've tried many times but I've failed.

Here is the original question in Hebrew:

n טענה כלשהי לגבי מםפר טבעי $P(n)$ תהי

אם מתקימיים שני התנאים הבאים:

1- הטענה $P(0)$ נכונה

2- לכל n>0, $P(n)$ נכונות הטענה $P(n-1)$ גוררת את נכונות הטענה

אז $P(n)$ נכונה לכל מספר טבעי n

הוכיחו את נכונות משפט זה

Answer 1

Your question seems somewhat unclear to me, as it stands, but I'll answer the one in the title, and if the question is updated, I'll address that too.

Mathematical induction can be taken as its own axiom, independent from the other (though, as comments point out, it can be proven as a theorem in common systems like ZF). That is to say, it is more akin to statements like: $$x\cdot (y+1)=x\cdot y + x$$ which are often taken to be part of the definition of multiplication and may not be derivable from more basic statements. The point behind such definitions is to capture some intuitive idea - the above starts to capture the distributive property of multiplication, which we know from intuition to be a reasonable idea. Yet, it is possible that we could not prove the above statement without taking it as an axiom.

Induction basically says every natural number can be "reached" from zero. That is, if we have proven the statements:

• $P(1)$ is true
• $P(n)\rightarrow P(n+1).$

Then, we can build a proof for every natural number. For instance, if we wanted to know that $P(5)$ was true, we could infer that, since $P(1)$ is true and $P(1)\rightarrow P(2)$, we have $P(2)$. But $P(2)\rightarrow P(3)$ and $P(3)\rightarrow P(4)$ and $P(4)\rightarrow P(5)$, thus we can deduce $P(5)$ too. Induction merely says that $P(n)$ must be true for all natural numbers because we can create a proof like the one above for every natural. Without induction, we can, for any natural $n$, create a proof for $P(n)$ - induction just formalizes that and says we're allowed to jump from there to $\forall n[ P(n)]$.

Answer 2

Consider the following definition of mathematical induction (adapted from David Gunderson's book Handbook of Mathematical Induction):

---

Principle of mathematical induciton: For some fixed integer $b$, and for each integer $n\geq b$, let $S(n)$ be a statement involving $n$. If

1. $S(b)$ is true, and
2. for any integer $k\geq b, S(k)\to S(k+1)$,

then for all $n\geq b$, the statement $S(n)$ is true.

---

Mathematical induction's validity as a valid proof technique may be established as a consequence of a fundamental axiom concerning the set of positive integers (note: this is only one of many possible ways of viewing induction--see the addendum at the end of this answer). The following statement of this axiom is adapted from John Durbin's book Modern Algebra, wherein it is called the Least Integer Principle, but it is often referred to as the Well-Ordering Principle or WOP. The principle is as follows:

Well-Ordering Principle: Every nonempty set of positive integers contains a least element.

The validity of mathematical induction, in this context where we are using the WOP to prove the validity of mathematical induction, is established by using a proof by contradiction. This proof will contain several "steps" or "parts." Before giving all of the steps to the proof of mathematical induction, it may be useful to reformulate the definition of the proof technique in terms of the notation that will be used throughout the sequence of steps in the explanation (for consistency and facilitated understanding):

---

Reformulated principle of mathematical induction: For some fixed integer $1$, and for each integer $n\geq 1$, let $S(n)$ be a statement involving $n$. If

1. $S(1)$ is true, and
2. for any integer $k\geq 1, S(k)\to S(k+1)$,

then for all $n\geq 1$, the statement $S(n)$ is true.

Let 1 and 2 above be denoted by $(\dagger)$ and $(\dagger\dagger)$, respectively.

---

Steps of the proof that mathematical induction is a consequence of the WOP:

1. Start by supposing that $S(1)$ is true and that the proposition $S(k) \rightarrow S(k+1)$ is true for all positive integers $k$, i.e., where $(\dagger)$ and $(\dagger\dagger)$ hold as indicated above.

2. The goal is to verify whether or not $S(n)$ is true for all $n \geq 1$ if $S(1)$ and $S(k) \rightarrow S(k+1)$ are true. The statement of mathematical induction above indicates that $S(n)$ will logically follow if $S(1)$ and $S(k) \rightarrow S(k+1)$ are true, but does $S(n)$ really follow if $(\dagger)$ and $(\dagger\dagger)$ are true? If yes, then mathematical induction is a valid proof technique. If not, then it is mere rubbish.

3. We are skeptics, and we think that mathematical induction is a sham (hint: a proof by contradiction is about to take place). Our skepticism induces us to assume that there is at least one positive integer for which $S(n)$ is false [keep in mind that we are assuming that $(\dagger)$ and $(\dagger\dagger)$ are true, albeit we are disputing whether or not $S(n)$ really follows from their truthfulness]. Surely there is at least one positive integer for which $S(n)$ is false even though $S(1)$ and $S(k) \rightarrow S(k+1)$ are true.

4. Let $\mathcal{P}$ denote the set of all positive integers for which $S(n)$ is false. Is this set empty? We think not---after all, we are assuming that there is at least one positive integer, say $\ell$, for which $S(n)$ is false; that is, the assumption is that $S(\ell)$ is false, where $\ell \in \mathcal{P}$. Are there other positive integers in $\mathcal{P}$? Perhaps, but we cannot say for certain at the moment. We can, however, declare with certainty that $\mathcal{P}$ has a least element by the well-ordering principle. We let the least element of $\mathcal{P}$ be $\ell$ without loss of generality.

5. Since $S(1)$ is true, we know that $\ell \neq 1$, and because $\ell$ is positive and greater than $1$, we also know that $\ell -1$ must be a positive integer. Moreover, because $\ell -1$ is less than $\ell$, it should be clear that $\ell -1$ cannot be in $\mathcal{P}$ [this is because $\ell$ is the least element in $\mathcal{P}$, meaning that any lesser positive integer cannot be in $\mathcal{P}$]. Notationally, we have it that $\ell \in \mathcal{P}$ and $(\ell - 1) \notin \mathcal{P}$. What does this mean? Since $(\ell - 1) \notin \mathcal{P}$ and $\ell -1$ is a positive integer, and because $\mathcal{P}$ is the set of all positive integers for which $S(n)$ is false, it must be that $S(\ell-1)$ is true.

6. Finally, recall that we maintained that $(\dagger\dagger)$ was true; that is, $S(k) \rightarrow S(k+1)$ is true for any integer $k \geq 1$. Since $\ell$ and $\ell -1$ are both positive integers, we may let $k = \ell -1$ and $k+1 = \ell$. Substituting these values into the implication that we assume to be true, we get that $S(\ell-1) \rightarrow S(\ell)$. Do you see the problem now (and hence the conclusion of the proof by contradiction)?

7. By supposing that $(\dagger)$ and $(\dagger\dagger)$ held while also supposing that $S(n)$ was false for some positive integer $\ell$, we deduced through a series of steps that $S(\ell-1) \rightarrow S(\ell)$ [by $(\dagger\dagger)$ where $k = \ell -1$ and $k+1 = \ell$]. What is wrong with this? Simply consider the following three assertions that occur within the proof:

   • $S(\ell-1)\to S(\ell)\qquad$ [True---by supposition $(\dagger\dagger)$]
   • $S(\ell)\qquad$ [False---because of the assumption that $S(n)$ was false for $\ell\in\mathbb{Z^+}$]
   • $S(\ell-1)\qquad$ [True---by the well-ordering principle]

   The logical issue should now be apparent. We know $S(\ell-1) \rightarrow S(\ell)$ is true by our original supposition, but this implication cannot be true if $S(\ell)$ is false. Why? Because an implication of the form $p \rightarrow q$ is only false when the hypothesis, $p$, is true and the conclusion, $q$, is false. In our own case, since $S(\ell-1)$ is true, the implication $S(\ell-1) \rightarrow S(\ell)$ is only true when $S(\ell)$ is also true, thus contradicting the choice of $\ell$. Consequently, $S(n)$ must be true for every positive integer $n$.

---

Addendum: It may be of interest to other students taking discrete mathematics courses that the form of induction proved above (often referred to simply as "induction") is actually equivalent to both strong induction and the WOP. This may be surprising, but there is a good paper about the Equivalence of Three Variations on Inducton for readers who are interested.

The basic idea behind the equivalence proofs is as follows:

1. Strong induction implies Induction.
2. Induction implies Strong Induction.
3. Well-Ordering of $\mathbb{N}$ implies Induction [This is the proof outlined in this answer but with much greater detail]
4. Strong Induction implies Well-Ordering of $\mathbb{N}$.

Equivalence of Induction, Strong Induction, and Well-Ordering on $\mathbb{N}$ follows after having proved the four implications outlined above (the paper linked to contains details of the proof(s)).

The answer I provided takes care of (3) above, but you can explore the other three to show equivalence if desired.

Answer 3

If it feel strange that such a strong proof technique has been placed, almost like cheating, in the definition of the natural numbers, one must bear in mind that induction only is valid in the formal model. There is an ambiguity in our mind, where we might mix up the numbers we obtained from reality with the objects in the slick model of Peano.

Induction is an important part of the definition of the model of natural numbers. If one omit the axiom of induction from the Peano axioms, $\Bbb N$ isn't well defined and larger sets can satisfy the axioms.

The axiom of induction ensures that $\Bbb N$ is the minimal set that satisfies the other axioms.

To see this, let $P(n)\iff n\in N$, where $N$ satisfies the other axioms of Peano. Then the axiom of induction states:

$0\in N$ and $(n\in N\implies n+1\in N)$ implies that for all $n\in\Bbb N$ it holds that $n\in N$. That is, $\Bbb N\subseteq N$.

Also, the minimal $\Bbb N \implies$ principle of induction.

If we can't use axioms for proving theorems, I believe nothing can be proved.

Answer 4

Mathematical induction is definitely the black sheep of common proof methods.

Common proof methods include:

• Proof by contradiction
• Direct proof
• Proof by exhaustion
• Proof by induction

I'm not sure what else a high school geometry text book might discuss, but let's go with that. The first three all pertain to logic. The fourth pertains to the natural numbers.

Do you agree...

that every subset of the natural numbers $S$ that

• contains 1, and
• if it contains some number $a$, then it contains $a+1$

must be the natural numbers?

Then you believe proof by induction works.

That is proof by induction. Say you want to prove that $1+\cdots+n=\frac{(n)(n+1)}{2}$ for all natural numbers $n$. Then let $S$ be the set of all numbers (!!) where that property is true (!!). Now proof by induction looks exactly like that pretty agreeable property of the natural numbers I just stated above.

Answer 5

$P(1)$ is given.

With $n=2$, $P(1)\to P(2)$.

With $n=3$, $P(2)\to P(3)$.

With $n=4$, $P(3)\to P(4)$.

$\cdots$

You can continue to establish any $P(n)$.

Answer 6

Formally, induction is an axiom or a consequence of other axioms.

Informally, it can be seen as similar to a proof by contradiction, perhaps something like:

Let $n$ be the smallest value for which $P(n)$ is false.

Unless $n$ is the smallest possible value in $\mathbb{N}$ (i.e. $1$, or if you prefer $0$), we know $P(n-1) \implies P(n)$, so if $P(n)$ is false then so too is $P(n-1)$ contradicting the definition of $n$.

Meanwhile $n$ cannot be the smallest possible value in $\mathbb{N}$, as we know that $P(1)$ was true.