Mathematical Proof/Methods of Proof

Template:Nav There are many different ways to prove things in mathematics. This chapter will introduce some of those methods.

Introduction

In this chapter, for every method of proof introduced, we will discuss it in this manner:

1. Explaining Template:Colored em the method works, by considering its underlying Template:Colored em.
2. Introducing Template:Colored em to use the method.
3. Giving examples of using the method (and possibly also some previous method introduced) to prove some results.

Before introducing the first proof method, let us go through the meanings of some frequently used terms in mathematics books (some are already used in previous chapters actually), which are used more frequently starting from this chapter.

• Definition: an explanation of meaning of a term.
• Theorem: an important and interesting true mathematical statement.

• Proposition: a (relatively) less important theorem.

• Lemma: a true mathematical statement that is useful in establishing the truth of other true statements, and is less important than a theorem.
• Corollary: a true mathematical statement that can be deduced from a theorem (or proposition) simply.
• Proof: an explanation of why a statement is true.
• Axiom: a true mathematical statement whose truth is accepted Template:Colored em.
• Conjecture: a statement that is Template:Colored em to be true, but is Template:Colored em proven to be true.

Direct proof

Many mathematical theorems can be expressed in the form of "$\mathrm{\forall }x\in S,P(x)⟹Q(x)$, in which $P(x)$ and $Q(x)$ are Template:Colored em about elements $x$ in a set $S$ . This expression means "If $P(x)$ then $Q(x)$" is true for every $x\in S$. However, in practice, we rarely include the phrase "is true", and usually just write the theorem in the form of "For every $x\in S$, if $P(x)$, then $Q(x)$." Sometimes, we write instead "Let $x\in S$. If $P(x)$, then $Q(x)$.", which has the same meaning.

In some situations, the statement is not stated in such a form Template:Colored em, but can be Template:Colored em in such a form. For example, the statement "The square of an even integer is even." can be expressed as "For every $x\in \mathbb{Z}$, $x$ is even $⟹$ $x^2$ is even.", or "For every $x\in \mathbb{Z}$, if $x$ is even, then $x^2$ is even.", or "Let $x\in \mathbb{Z}$. If $x$ is even, then $x^2$ is even.", etc.

Now, we will introduce the first proof method to prove statements in such a form, which is known as Template:Colored em. As suggested by its name, this method is quite "direct", and is probably the simplest method among all methods discussed in this chapter.

Consider the statement "$\mathrm{\forall }x\in S,P(x)\to Q(x)$". We would like to prove that it is true. Suppose $P(x_0)$ is Template:Colored em for some $x_0\in S$. Then, the conditional $P(x_0)\to Q(x_0)$ must be true for this $x_0$ by definition, regardless of the truth value of $Q(x_0)$. Hence, in the proof, we do not need to consider those $x\in S$ for which the hypothesis $P(x)$ is false.

Because of this, to give a Template:Colored em of "$\mathrm{\forall }x\in S,P(x)⟹Q(x)$", we first Template:Colored em $P(x)$ is Template:Colored em (So, we are considering every $x\in S$ for which $P(x)$ is true.), and then proceed to show that $Q(x)$ is true for every such $x$ (or else the conditional $P(x)\to Q(x)$ will be false).

This shows that $P(x)\to Q(x)$ is true for those $x\in S$ for which $P(x)$ is Template:Colored em, and this is enough to prove $P(x)\to Q(x)$ is true for Template:Colored em $x\in S$ (for which $P(x)$ may or may not be true), since we have mentioned that the conditional $P(x)\to Q(x)$ must be true for those $x\in S$ for which $P(x)$ is false.

Template:Colored example Template:Colored remark Template:Colored exercise Template:Colored exercise Template:Colored exercise Template:Colored exercise Template:Colored example Template:Colored remark Template:Colored example Template:Colored remark Template:Colored exercise Combining the two results in the previous example and exercise, we get an "if and only if" result:

For every $x\in ℝ$, we have $x^2-x-2<-2$ if and only if $0<x<1$.

In other words, using set language, $$\{x\in ℝ:0<x<1\}=\{x\in ℝ:(x-1{)}^2<1\}.$$ (Both sets represent the curve (strictly) under the horizontal line $y=-2$ in the above graph.)

Letting $P(x)$ and $Q(x)$ be the open statement "$x^2-x-2<-2$" and "$0<x<1$" respectively, we can express the above result symbolically: $$\mathrm{\forall }x\in ℝ,P(x)⟺Q(x).$$ Recall that "$P(x)⟺Q(x)$" means "$P(x)⟹Q(x)$" Template:Colored em "$Q(x)⟹P(x)$". So, to give a direct proof to the statement in the form of "$\mathrm{\forall }x\in S,P(x)⟺Q(x)$", a usual way is to break the proof into two parts:

1. proving that $\mathrm{\forall }x\in S,P(x)⟹Q(x)$ (known as the "Template:Colored em" part, or "$\Rightarrow$" direction)
2. proving that $\mathrm{\forall }x\in S,Q(x)⟹P(x)$ (known as the "Template:Colored em" part, or "$\Leftarrow$" direction)

Proofs related to congruence of integers

After introducing the method of direct proof, let us apply this method on proving some results relating to congruence of integers. Before this, let us introduce the concept of congruence of integers. We begin by a motivation for the definition of congruence of integers.

We know that an integer $x$ is either even or odd, i.e., can be expressed as $2k$ or $2k+1$ for some integer $k$, according to whether the remainder is 0 or 1 when $x$ is divided by 2. Thus, if two integers $x$ and $y$ have the same remainder when divided by 2 (i.e., have the same parity), then the difference $x-y$ can be proved to be a multiple of 2 (it can be proved that the converse is also true). Similarly, an integer can be expressed as $3k,3k+1$ or $3k+2$ for some integer $k$, according to whether remainder is 0, 1 or 2 when $x$ is divided by 3. Hence, if two integers $x$ and $y$ have the same remainder when divided by 3, then the difference $x-y$ can be proved to be a multiple of 3 (the converse is also true).

Hence, "two integers have the same remainder when divided by some integer $k$" is equivalent to "their difference is a multiple of $k$". This leads us to the following definition. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored exercise Template:Colored example Now, let us apply direct proof to prove some results related to the congruence of integers. Template:Colored theorem

Proof. We will only prove the compatibility with addition and multiplication. The proof of other two compatibilities is left to the following exercise.

Compatibility with addition: Assume that $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$. Then, $a-b=n{k}_1$ and $c-d=n{k}_2$ for some $k_1,k_2\in \mathbb{Z}$. Thus, $$(a+c)-(b+d)=(a-b)+(c-d)=n{k}_1+n{k}_2=n(k_1+k_2).$$ Since $k_1+k_2\in \mathbb{Z}$, we have $a+c\equiv b+d(\mathrm{mod}n)$.

Compatibility with multiplication: Assume that $a\equiv b(\mathrm{mod}n)$ and $c\equiv d(\mathrm{mod}n)$. Then, $a-b=n{k}_1$ and $c-d=n{k}_2$ for some $k_1,k_2\in \mathbb{Z}$. Thus, $$ac-bd=ac-bc+bc-bd=c(a-b)+b(c-d)=cn{k}_1+bn{k}_2=n(c{k}_1+b{k}_2).$$ Since $c{k}_1+b{k}_2\in \mathbb{Z}$, we have $ac\equiv bd(\mathrm{mod}n)$.

$◻$

Template:Colored remark Template:Colored exercise Template:Colored exercise In the above result, everything is with the same "modulo $n$". It is then natural to ask whether there are any results for different "modulo". The answer is yes, and to discuss a result, we need the concept of Template:Colored em integers. Template:Colored definition Template:Colored remark Template:Colored example Template:Colored theorem

Proof. Omitted.

$◻$

Using this result, we can deduce the following result: Template:Colored theorem

Proof. Assume $a\equiv b(\mathrm{mod}m)$, $a\equiv b(\mathrm{mod}n)$, and $m,n$ are relatively prime. Then, we have $a-b=k_{1}m$ and $a-b=k_{2}n$ for some $k_1,k_2\in \mathbb{Z}$. This means $k_{1}m=k_{2}n$. Also, $mx+ny=1$ for some $x,y\in \mathbb{Z}$. Multiplying both sides by the integer $k_1$, we get $$xm{k}_1+yn{k}_1=k_1.$$ Putting $m=\frac{k_{2}n}{k_1}$, we get $$x{k}_{2}n+yn{k}_1=k_1⟹n(x{k}_2+y{k}_1)=k_1.$$ Putting this into $a-b=k_{1}m$, we get $$a-b=mn(x{k}_2+y{k}_1).$$ Since $x{k}_2+y{k}_1\in \mathbb{Z}$, we have $a\equiv b(\mathrm{mod}mn)$.

$◻$

Template:Colored remark Template:Colored exercise Template:Colored example Template:Colored remark Template:Colored example Template:Colored example The following lemma is quite useful for proving results about congruence of integers. Template:Colored lemma

Proof. We separate the proof into Template:Colored em part and Template:Colored em part.

Existence part:

Case 1: $b<0$.

Then, we set $b^{\prime }=-b>0$ and $q^{\prime }=-q$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a=b^{\prime }{q}^{\prime }+r$, and also the inequality $0\le r\le |b^{\prime }|$ can be rewritten equivalently as $0\le r\le |b^{\prime }|$. Through this, we transform this case to case 2.

Case 2: $b>0$.

Subcase 1: $a<0$ and $b>0$.

Then, we set $a^{\prime }=-a$, $q^{\prime }=-q-1$, and $r^{\prime }=b-r$. After that, the equation $a=bq+r$ can be rewritten equivalently as $a^{\prime }=b{q}^{\prime }+r^{\prime }$ (this is equivalent to $-a=-bq-r$). Also, the inequality $0\le r\le |b^{\prime }|$ can be rewritten equivalently as $0\le r^{\prime }<|b|$. Through this, we transform this case to the subcase 2.

Subcase 2: $a\ge 0$ and $b>0$.

Set $q_1=0$ and $r_1=a\ge 0$. Then, we have $a=b{q}_1+r_1$.

Subsubcase 1: $r_1<b=|b|$. Take $q=q_1$ and $r=r_1$. Then, we have $$a=bq+r\text{ and }0\le r<|b|,$$ and we are done.

Subsubcase 2: $r_1\ge b$.

Set $q_2=q_1+1$ and $0\le r_2=r_1-b<r_1$. Then, we have $a=b{q}_2+r_2$ with $0\le r_2<r_1$. Since there are exactly $r_1$ nonnegative integers less than $r_1$, we need to repeat this process Template:Colored em $r_1$ times ($b\ge 1$, so $r_2$ is Template:Colored em the preceding integer of $r_1$) to get a $r_k$ such that $0\le r_k<|b|$ (and also a $q_k$).

So, we take $q=q_k$ and $r=r_k$. Then, we have $$a=bq+r\text{ and }0\le r<|b|,$$ and we are done.

Uniqueness part:

Assume there exists another pair of integers $q^{*}$ and $r^{*}$ (in addition to the pair of integers $q$ and $r$) such that $$a=b{q}^{*}+r^{*}\text{ and }0\le r^{*}<|b|.$$ Since we have also $$a=bq+r\text{ and }0\le r<|b|,$$ we get, by subtracting the two equations, $$0=b(q-q^{*})+r-r^{*}⟹b(q-q^{*})=r^{*}-r.$$

Also, by considering the above two inequalities, we get $$\begin{array}{cccc}& & 0\le & |r^{*}-r|<|b|\\ & \Rightarrow & 0\le & |b(q-q^{*})|<|b|\\ & \Rightarrow & 0\le & |b||q-q^{*}|<|b|\\ & \Rightarrow & 0\le & |q-q^{*}|<1& (b\ne 0)\\ & \Rightarrow & & |q-q^{*}|=0\\ & \Rightarrow & & q=q^{*}.\\ \end{array}$$ Putting it in the above equation, we get $0=r^{*}-r⟹r=r^{*}$.

Thus, we have $q=q^{*}$ and $r=r^{*}$.

$◻$

Proofs related to sets

The proofs related to sets are often in the form of

1. A set is a subset of another set.
2. A set equals another set.

To prove that a set is a subset of another set, we use the definition of subset:

A set $X$ is a subset of another set $Y$ if for every element $x$, if $x\in X$, then $x\in Y$.

Thus, we can employ direct proof to prove that a set is a subset of another set.

For the equality of two sets, recall that:

A set $X$ equals another set $Y$ if and only if $X\subseteq Y$ and $Y\subseteq X$.

Thus, to prove the equality of two sets, we often need to separate the proof into two parts: (i) proving that $X\subseteq Y$; (ii) proving that $Y\subseteq X$.

Template:Colored example Template:Colored example We can observe that to prove different laws for the sets, we just simply use the corresponding laws in logic to prove them. Hence, the proofs for other laws, e.g., commutative law and distributive law, are similar. Template:Colored exercise Template:Colored example Template:Colored example Template:Colored exercise Template:Colored example Template:Colored example Template:Colored exercise Template:Colored example Template:Colored example Template:Colored exercise

Proof by contrapositive

Recall that the Template:Colored em of a conditional $P\to Q$ is the statement $\sim Q\to \sim P$, which is Template:Colored em to the original conditional $P\to Q$. Hence, if we can show that $\sim Q⟹\sim P$, then it follows that $P⟹Q$. This gives us another method of proof, namely Template:Colored em.

A Template:Colored em of the statement $\mathrm{\forall }x\in S,P(x)⟹Q(x)$ is a Template:Colored em of $\mathrm{\forall }x\in S,\sim Q(x)⟹\sim P(x)$. That is, we first assume that $\sim Q(x)$ is true, and proceed to show that $\sim P(x)$ is true. In other words, we first assume that $Q(x)$ is Template:Colored em, and proceed to show that $P(x)$ is Template:Colored em.

Generally, when we encounter a statement $\mathrm{\forall }x\in S,P(x)⟹Q(x)$, and observe that the consequent $Q(x)$ is "simpler" than the hypothesis $P(x)$, using proof by contrapositive is usually more preferable. Template:Colored example Template:Colored example Template:Colored remark Template:Colored example Template:Colored example Template:Colored exercise Template:Colored example Template:Colored exercise Template:Colored exercise

Proof by cases

In the previous sections, we have actually employed the method of Template:Colored em already. It is natural to use this method when we need to break down a problem into several cases, and then tackle every case individually ("divide and conquer"). Sometimes, we may even need to further divide a case into several subcases. The following are some typical cases:

1. an integer is even or odd;
2. a real number is less than 0, equal to 0, or greater than 0;
3. for two nonzero real numbers $x$ and $y$, either $xy>0$ or $xy<0$.

• For every of the cases, it can be divided into two subcases:

1. $xy>0$: ($x>0$ and $y>0$) or ($x<0$ and $y<0$)
2. $xy<0$: ($x>0$ and $y<0$) or ($x<0$ and $y>0$)

But, we should be aware that when we use proof by cases to prove that "$\mathrm{\forall }x\in S,\dots$", the cases should cover all possibilities, i.e., all $x\in S$. Template:Colored example Template:Colored example Template:Colored remark Template:Colored exercise The following inequality is quite important in mathematics. Template:Colored theorem

Proof.

Case 1: $x\ge 0$ and $y\ge 0$.

Then, $x+y\ge 0$, and so $$|x+y|=x+y=|x|+|y|.$$

Case 2: $x<0$ and $y<0$.

Then, $x+y<0$, and so $$|x+y|=(-x)+(-y)=|x|+|y|.$$

Case 3: one of $x$ and $y$ is nonnegative, and the other is negative.

WLOG, assume $x\ge 0$ and $y<0$.

Subcase 1: $x+y\ge 0$.

Then, $$\begin{array}{cc}|x+y|& =x+y\\ & <x+(-y)& (y<0<-y)\\ & =|x|+|y|.\end{array}$$

Subcase 2: $x+y<0$.

Then, $$\begin{array}{cc}|x+y|& =-(x+y)\\ & =(-x)+(-y)\\ & \le x+(-y)& (-x\le 0\le x)\\ & =|x|+|y|.\end{array}$$

So, we have the desired inequality for every $x,y\in ℝ$.

$◻$

Proof by contradiction

Another important method of proof is Template:Colored em.

Let $P$ be a statement. Now, suppose we want to prove that $P$ is true. If we can show that the conditional $\sim S\to 𝐅$ is true (i.e., $\sim S⟹𝐅$), then the truth table for conditional tells us that $\sim S$ Template:Colored em false, and hence $S$ must be true, as desired.

The truth table: $$\begin{array}{cccc}S& \sim S& 𝐅& \sim S\to 𝐅\\ T& F& F& T\\ F& T& F& F\end{array}$$ In words, the method of proof by contradiction is as follows: we first assume that the statement we want to prove to be true is Template:Colored em, and then proceed to show that this gives a Template:Colored em, and therefore our assumption must be wrong. That is, it is impossible for the statement to be false since it leads to something "absurd". Hence, the statement is true.

The name of Template:Colored em comes from the fact that the assumption that the statement is false is later Template:Colored em by some other fact. This is also known as Template:Colored em, which means reduction to absurdity.

In general, we often use the method of proof by contradiction when the statement we want to prove is Template:Colored em, e.g. "There is no ....", "There does not exist ...", etc.

Also, to indicate to the reader that we are using proof by contradiction, it is recommended that we write "assume to the contrary that ..." (or something similar) instead of just "assume ..." for the assumption that the statement is false. Template:Colored example Template:Colored example Template:Colored example The following is a typical example in introducing proof by contradiction: Template:Colored example The following example is another typical example for demonstrating proof by contradiction. But before discussing it, we need to introduce the following theorem since it is used in the proof. Template:Colored theorem

Proof. We will prove this theorem after introducing Template:Colored em.

$◻$

Template:Colored remark Template:Colored example Template:Colored remark We can also use proof by contradiction to prove that a statement "$\mathrm{\forall }x\in S,P(x)\to Q(x)$" is true. We first assume that the negation of the statement, i.e., "$\mathrm{\exists }x\in S,P(x)\wedge (\sim Q(x))$" is true, and proceed to arrive at a contradiction. (Recall that $P\to Q⟺(\sim P)\vee Q$. So, $\sim (P\to Q)⟺P\wedge (\sim Q)$.) Thus, to prove that $\mathrm{\forall }x\in S,P(x)⟹Q(x)$ Template:Colored em, we assume that there exists $x\in S$ such that $P(x)$ is true and $Q(x)$ is false, and then deduce a contradiction. Template:Colored example Template:Colored exercise Template:Colored example Template:Colored exercise Template:Colored example Sometimes we can prove a statement using multiple methods: Template:Colored example Template:Colored exercise We can see that when proving a statement "$\mathrm{\forall }x\in S,P(x)⟹Q(x)$", we may be able to use both proof by contrapositive and proof by contradiction. However, the two proofs are different, and we will compare them in the following table:

Proving that "$\mathrm{\forall }x\in S,P(x)⟹Q(x)$."

	Proof by contrapositive	Proof by contradiction
Assumption	$\sim Q(x)$	$P(x)\wedge \sim Q(x)$
Goal	$\sim P(x)$	$𝐅$

From this table, we can see that the proof by contradiction is more advantageous in terms of assumption, since it has one more "help" from $P(x)$ (when we assume $P(x)\wedge \sim Q(x)$, we can use both $\sim Q(x)$ and $P(x)$.) However, in terms of goal, the proof by contrapositive is more advantageous since the goal is more clear ($\sim P(x)$), while for the proof by contradiction, it is not clear that what the form of the contradiction is. There can be many "ways" for arriving at a contradiction (compare the contradiction in the proof of "$\sqrt{2}$ is irrational" vs. that of "there are infinitely many primes").

Existence proof

Consider the statement "$\mathrm{\exists }x\in S,P(x)$". This statement is true if $P(x)$ is true for Template:Colored em $x\in S$. Otherwise, it is false. Thus, to prove such kind of statement, it suffices to find Template:Colored em element $x\in S$ such that $P(x)$ is true, and this is known as an existence proof. In particular, we should verify that the choice of element $x$ is actually belonging to $S$ and $P(x)$ is actually true for that choice. Template:Colored example Template:Colored remark Template:Colored example The following example demonstrates a more advanced version of existence proof: Template:Colored em. Template:Colored example Template:Colored remark Template:Colored exercise

Disproof

Consider the statement "$\mathrm{\forall }x\in S,P(x)$.". Suppose we somehow believe that the statement is Template:Colored em. Then, we want to prove that it is false, i.e., prove that "$\mathrm{\exists }x\in S$ such that $P(x)$ is false." An element $x_0\in S$ for which $P(x_0)$ is false is known as a Template:Colored em of the statement, and a process of showing that the statement is Template:Colored em (in other words, Template:Colored em the statement) is called a Template:Colored em of the statement. One counterexample is enough to disprove the statement. Template:Colored example Template:Colored example To disprove the statement "$\mathrm{\forall }x\in S,P(x)\to Q(x)$, we show that there exists an element $x_0\in S$ such that $P(x_0)\to Q(x_0)$ is false, i.e., $P(x_0)$ is true and $Q(x_0)$ is false. Template:Colored example To disprove the statement "$\mathrm{\exists }x\in S,P(x)$", we need to show that there is Template:Colored em such $x$. That is, we need to show that "$\mathrm{\forall }x\in S,\sim P(x)$" (the negation of statement) is true. In this case, we are Template:Colored em just constructing counterexamples. We have to prove that $\mathrm{\forall }x\in S,\sim P(x)$, instead of $\mathrm{\exists }x\in S,\sim P(x)$. Template:Colored example Often, before proving or disproving statements, the truth of falseness of them are Template:Colored em known, and we need to decide whether every of them is true or false. After that, we will prove it if it is true and disprove it otherwise. Of course, our decision is not perfectly accurate, and sometimes we make mistake, which leads us to do the opposite thing, i.e., proving a wrong statement or disproving a correct statement. Clearly, when we do such thing, we cannot succeed. However, the Template:Colored em of performing such wrong thing may give us some insights about what the correct direction is, and how to prove/disprove the statement.

To decide whether a statement is true or false, you may follow some tips below:

• Follow your mathematical intuition. As you have learnt more about mathematics, you may have intuition and idea about whether a statement is true or false, before proving/disproving it.
• Construct some simple examples. Such examples constructed may be a counterexample (for disproving "$\mathrm{\forall }\cdots$")/example (for proving "$\mathrm{\exists }\cdots$") if you are lucky. Even if they are not counterexamples/examples, you may observe some kind of patterns from it, which may give you some insights about how to prove/disprove the statement.

Proof by mathematical induction

The last proof method discussed in this chapter is Template:Colored em. This method is used to prove a statement in the form of "For every integer $n$ greater than or equal to an integer $m$, $P(n)$ is true.". That is, it is used to prove that a Template:Colored em of statements $P(m),P(m+1),P(m+2),\dots$ is true. Of course, we can prove that every of these statements is true one by one, but the principle of mathematical induction gives an alternative and more convenient method.

To Template:Colored em the principle of mathematical induction, we need the Template:Colored em. Before introducing it, we need the definition of Template:Colored em. Template:Colored definition Template:Colored example Now, one may ask that whether the set $\mathbb{N}$ is well-ordered. It may Template:Colored em that it is well-ordered. Here, we will just regard this as an Template:Colored em: Template:Colored axiom The well-ordering principle can then be used to prove (a less general version of) the principle of mathematical induction. Template:Colored theorem This theorem is quite intuitive: with the conditions satisfied, we have an "infinite chain of implications":

• $P(m)$ is true (by (i)).
• Thus, $P(m+1)$ is true (by (ii)).
• Thus, $P(m+2)$ is true (by (ii)).
• Thus, $P(m+3)$ is true (by (ii)) ...

But strictly speaking, this is not counted as a proof. We will give a formal (partial) proof to this theorem below:

Proof. Here we only prove the case where $m\in \mathbb{N}$.

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb{N}:P(n)\text{ is false}\}.$$ Since $S$ is a nonempty subset of $\mathbb{N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\ge m+1$, which means $s-1\ge m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Then, by the condition (ii), $P(s)$ is true (we have $s-1\ge m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least Template:Colored em of $S$ (in particular, $s\in S$).

$◻$

Template:Colored remark Using the principle of mathematical induction, to prove that the statement $P(n)$ is true for every integer $n\ge m$, it suffices to prove two things:

(i) $P(m)$ is true.

(ii) For every integer $k\ge m$, $P(k)⟹P(k+1)$.

Thus, proof in this form is a two-step process. We often call the proof of (i) as the Template:Colored em or Template:Colored em, and the proof of (ii) is called the Template:Colored em. In particular, when we prove (ii), we usually use the method of direct proof, and first assume $P(k)$ is true for Template:Colored em integer $k$ with $k\ge m$. Such assumption is often called the Template:Colored em. Template:Colored example Template:Colored remark Template:Colored exercise We can use the proof by mathematical induction for proving some inequalities also: Template:Colored example Template:Colored exercise Template:Colored example Template:Colored example Template:Colored exercise

The strong form of induction

In this section, we will discuss a stronger form of mathematical induction. Sometimes, we need this form of mathematical induction since merely assuming "$P(k)$ is true ..." in the inductive hypothesis may not be enough to show that $P(k+1)$ is true. We may need some more helps, particularly the fact that the statement is true for Template:Colored em from the basis step to the given $k$. That is, if "$m$" is 1, then we assume $P(1),\dots ,P(k)$ are all true.

Since "$P(1)\wedge P(2)\wedge \cdots \wedge P(k)$" is Template:Colored em than "$P(k)$", we have the name "the Template:Colored em form of induction". Template:Colored theorem This theorem is also quite intuitive: with the conditions satisfied, we get an "infinite chain of implications":

1. $P(m)$ is true by (i).
2. Because of 1., $P(m+1)$ is true by (ii).
3. Because of 1. and 2., $P(m+2)$ is true by (ii).
4. Because of 1., 2., and 3., $P(m+3)$ is true by (ii) ...

Proof. The proof for the strong form of induction is similar to that of the principle of mathematical induction. We just need to modify some parts of the proof. The Template:Color is the modified part.

Here we only prove the case where $m\in \mathbb{N}$.

Assume to the contrary that the theorem is false. Then, the conditions (i) and (ii) are satisfied by the statements, but there exist some positive integers $n$ for which $P(n)$ is false. Now, let the set $$S=\{n\in \mathbb{N}:P(n)\text{ is false}\}.$$ Since $S$ is a nonempty subset of $\mathbb{N}$, by the well-ordering principle, $S$ contains a least element. Let us assume $s$ to be the least element.

Since $P(m)$ is true by the condition (i), $m\notin S$. This means the least element $s$ cannot be $m$. Hence, $s\ge m+1$, which means $s-1\ge m$.

Since $s$ is the least element of $S$, we have $s-1\notin S$, i.e., $P(s-1)$ is a true statement. Template:Color Then, by the condition (ii), $P(s)$ is true (we have $s-1\ge m$). It follows that $s\notin S$. But this contradicts to our assumption that $s$ is the least Template:Colored em of $S$ (in particular, $s\in S$).

$◻$

Hence, to prove that the statement $P(n)$ is true for every $n\ge m$ by the strong form of induction, we need to prove

(i) the basis step: $P(m)$ is true; and (ii) the inductive step: for every integer $k\ge m$, if $P(m),P(m+1),\dots ,P(k)$ are true (the inductive hypothesis), then $P(k+1)$ is true.

We usually use the strong form of induction to prove results that are related to Template:Colored em. Template:Colored example Template:Colored exercise Template:Colored example Template:Colored remark Template:Colored exercise Template:Nav Template:BookCat