Proof writing: how to write a clear induction proof?

Question

What is an effective way to write induction proofs?

Essentially, are there any good examples or templates of induction proofs that may be helpful (for beginners, non-English-native students, etc.)?

To guide readers, please state whether your answer handles:

• Case 1: a simple induction $(P_n \implies P_{n+1}$), or
• Case 2: a strong induction ($P_1,\ldots,P_n \implies P_{n+1}$), or
• Case 3: a more exotic induction (e.g. over $\Bbb Q$ on $|p|+q$).

PS: I have seen many induction related questions, and very often the problem lies with the OP's lack of a proper methodology (or style) in writing the proof whereas the answers focus on the particular case of the OP's question. The matter of style is obviously subjective, but it seems to me that the "craft" of writing good proofs is almost as important as understanding underlying concepts, so advice on proper proof-writing practices should fall within the scope of MSE (under the proof-writing tag).

Answer 1

A proposal for case 1 (simple induction):

Here are some generic recommendations for beginners I have given in previous answers (here or here):

• Write down in full length the statement $P_n$ to be proven at rank $n$, and the range of values $n$ over which $P_n$ should stand
• Clearly mark the anchors of the induction proof: base case, inductive step, conclusion

Let's prove that $\forall q \in \Bbb C - \{1\}$, $1+q+\cdots+q^n = \tfrac{1-q^{n+1}}{1-q}$.

1. We start by fixing $q \in \Bbb C- \{1\}$.

2. For $n \in \Bbb N$, we define the statement $\displaystyle P_n\;:\; \sum_{k=0}^{n} q^k = \tfrac{1-q^{n+1}}{1-q}$.

3. Base case: if $n=0$, the left-hand-side term (LHS) in $P_0$ has only term equal to $1$, and the RHS is equal to $\tfrac{1-q}{1-q} = 1$. We have thus proven that $P_0$ is true.

4. Inductive step: let $n$ be an integer greater than $1$, and let's assume that $P_{n-1}$ is true. Then: $$\begin{align} \sum_{k=0}^{n} q^k & = \sum_{k=0}^{n-1} q^k + q^n \quad & \text{(by definition)}\\ & = \color{red}{\tfrac{1-q^n}{1-q}} + q^n & \color{red}{\text{(since $P_{n-1}$ is assumed to be true)}} \\ & = \frac{1-q^n + q^n(1-q)}{1-q} = \frac{1-q^{n+1}}{1-q} \end{align}$$ We have just showed that $P_{n-1} \implies P_n$.

5. Conclusion: since $P_0$ is true and $\forall n \ge 1$, $P_{n-1} \implies P_n$, $P_n$ holds for all $n\in \Bbb N$. QED

Answer 2

A (canonical, if not exciting) proposal for case 2 (strong induction):

Let's prove that every integer $\ge 2$ can be expressed as a product of one or more prime numbers.

1. For $n \ge 2$, we define the statement $P_n \;:\; \forall k \in \{2,\ldots,n\}$, there exists a (finite) sequence of prime numbers $p_{n_1}, \ldots, p_{n_k}$ such as $k = p_{n_1} \ldots p_{n_k}$.

2. Base case: if $n=2$, $P_2$ is trivial since $2$ is prime.

3. Inductive step: let $n$ be an integer greater than $2$ and let's assume that $P_{n}$ is true. Then:

   • either $n+1$ is prime, and $P_{n+1}$ is trivially true (since $n+1=n+1$ is a product of (one) prime(s) and the cases $\le n$ are true by the induction assumption);
   • or $n+1$ is composite; then, by definition, $n+1$ can be expressed as $n+1 = uv$ with $u,v$ integers $>1$. But then $ u,v \in \{2,\ldots,n\}$ (since $u = (n+1)/v < n+1$) and by the induction assumption, $u$ and $v$ can be expressed as products of primes: $u = p_{n^u_1}\ldots p_{n^u_u}$ and $v = p_{n^v_1}\ldots p_{n^v_v}$. But then $n+1 = p_{n^u_1}\ldots p_{n^u_u}p_{n^v_1}\ldots p_{n^v_v}$, which is a product of primes, and again $P_{n+1}$ is true.

4. Conclusion: since $P_2$ is true and $\forall n \ge 2$, $P_n \implies P_{n+1}$, $P_n$ holds for all $n \ge 2$. QED

Answer 3

Here is my template for case #$1$:

As an example, let's prove by induction that $\sum\limits_{k=0}^{n-1}2\cdot3^k=3^n-1$.

---

First, show that this is true for $n=1$:

$\sum\limits_{k=0}^{1-1}2\cdot3^k=3^1-1$

Second, assume that this is true for $n$:

$\sum\limits_{k=0}^{n-1}2\cdot3^k=3^n-1$

Third, prove that this is true for $n+1$:

$\sum\limits_{k=0}^{n}2\cdot3^k=$

$\color{red}{\sum\limits_{k=0}^{n-1}2\cdot3^k}+2\cdot3^n=$

$\color{red}{3^n-1}+2\cdot3^n=$

$3\cdot3^n-1=$

$3^{n+1}-1$

Please note that the assumption is used only in the part marked red.

Answer 4

Initial comments: This is an excellent question in my opinion and is just what the proof-writing tag is for. Unfortunately, there are often many problems plaguing beginners when it comes to induction proofs:

• Why induction is a valid proof technique should be understood at the outset, and this is rarely the case.
• Less relevant in high school or undergrad, but certainly important on MSE--it is expected for one to be able to typeset their math correctly. This often means taking the time to learn some MathJax, ${\rm\LaTeX}$, or a hybrid of these, something that takes a good bit of time.
• In order to be able to communicate a proof effectively, one must necessarily understand how to write well, a talent often under appreciated and underdeveloped amongst mathematicians.

The list could go on and on, but those are some of the more salient points. That being said, I will provide a template for writing up nice, polished induction proofs, and then I will detail the rationale for this template, both adopted from David Gunderson's marvelous book Handbook of Mathematical Induction. More specifically, what has been adapted is from the chapter "The written MI proof" (yes, there's an entire chapter devoted just to how to effectively write induction proofs--pgs 109-119, specifically). Finally, I will conclude by showing how one might use this template to prove the statement $\prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}$ for $n\geq 2$.

---

Template

Note: In the above template, if the proof is by strong induction, then the induction hypothesis should be replaced with "assume that for each $j, 3\leq j\leq k$, $$ \text{$S(j) : $ (write out what $S(j)$ says)} $$ holds. Also, in the sequence of equations, at the point where the induction hypothesis is invoked, either write "by IH" or mention which statements of the IH are used (e.g., by $S(4)$ and $S(k)$).

---

Rationale for Template

Suppose that a particular statement regarding $n$ is to be proved for $n\geq 3$.

1. Define the statement that needs to be proved. For example: "For each $n\geq 3$, let $S(n)$ be the statement $\ldots$". If there is more than one variable, be careful of quantification; for example, the expression $$ \text{For each $n\geq 3$ let $S(n)$ be the statement that for all $m\leq n$ $\ldots$} $$ is different from $$ \text{For each $n\geq 3$ and all $m\leq n$, let $S(n)$ be the statement that $\ldots$} $$ In the second expression, the lower bound for $m$ is not stated, and it is not clear whether or not $S(n)$ depends on the particular value of $m$, so perhaps something like $$ \text{For each $n\geq 3$ and each $m$ satisfying $1\leq m\leq n$, let $S(m,n)$ be the statement $\ldots$} $$ is better. It might help to also identify in advance for which variables a particular sentence even makes sense, later restricting the variable to the cases that are being proved.

2. State the range of $n$ for which the statement is to be proved. For example:
   "To be proved is that for each integer $n\geq 3$, the statement $S(n)$ is true."

3. Base step: Write the words "Base step" and verify that the base case is true (giving reasons if it is not trivial). For example:
   Base step: $S(3)$ says $\ldots$ which is true.

4. Inductive step: Write out the words "Inductive step:"

5. State the inductive hypothesis. For simple mathematical induction, this will read like: For some fixed $k\geq 3$, assume that $S(k)$ is true. [Writing out precisely what $S(k)$ says is usually an excellent idea.] For strong induction, this will read something like: "For some fixed $k\geq 3$, assume that $S(3), S(4), \ldots, S(k)$ are all true," or "For some fixed $k\geq 3$, assume that for $3\leq j\leq k, S(j)$ is true." Labelling the inductive hypothesis with the words "inductive hypothesis" (or "IH") is often a useful practice for the novice.

6. State what needs to be proved, namely $S(k+1)$. It is highly recommended that one writes out $S(k+1)$ specifically so that one sees the required form of the conclusion in the inductive step.

7. Prove $S(k+1)$. If $S(n)$ is an equality (or inequality), it is best to start with one side of $S(k+1)$, and via a sequence of equalities (or inequalities), derive the other side. At the point where the inductive hypothesis is used, this should be mentioned either as a side comment "by $S(k)$", "by induction hypothesis", or even by putting the initials "IH" over the relevant equal sign.

8. Mention when the inductive step is done. For example, one might write "$\ldots$ completing the inductive step $S(k)\to S(k+1)$.", or simply "This completes the inductive step."

9. State the conclusion: "Therefore by mathematical induction, for all $n\geq 3, S(n)$ is true. $\Box$", using the symbol "$\Box$" to denote that the entire proof is complete (this symbol is even more shorthand for QED; more information about this may be found here). Some mathematicians prefer to quantify variables before they are used, as in "$\ldots$ for all $n\geq 3, S(n)$ is true." This is a good practice, as it reads more logically; however, remember to insert a comma (because "$n\geq 3\, S(n)$" might be meaningless) or an extra phrase like "$\ldots$ for $n\geq 3$, the statement $S(n)$ holds."

Somewhat surprisingly, in an attempt to simply memorize the format of an inductive proof, students often discover what was wrong with their previous formats. The novelty of the template is that it forces students, more or less, to understand their own inductive proofs.

---

Using the Template

Problem: Prove that for all $n\geq 2, \prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}$.

Solution: For any integer $n\geq 2$, let $S(n)$ denote the statement $$ S(n) : \prod_{i=2}^n\left(1-\frac{1}{i}\right)=\frac{1}{n}. $$

Base step ($n=2$): $S(2)$ says $\prod_{i=2}^2\left(1-\frac{1}{i}\right)=\frac{1}{2}$, and this is true because $$\prod_{i=2}^2\left(1-\frac{1}{i}\right)=1-\frac{1}{2}=\frac{1}{2}.$$

Inductive step $S(k)\to S(k+1)$: Fix some $k\geq 2$. Assume that $$ S(k) : \prod_{i=2}^k\left(1-\frac{1}{i}\right)=\frac{1}{k} $$ holds. To be proved is that $$ S(k+1) : \prod_{i=2}^{k+1}\left(1-\frac{1}{i}\right)=\frac{1}{k+1} $$ follows. Beginning with the left side of $S(k+1)$, \begin{align} \prod_{i=2}^{k+1}\left(1-\frac{1}{i}\right) &= \left[\prod_{i=2}^k\left(1-\frac{1}{i}\right)\right]\left(1-\frac{1}{k+1}\right)\tag{by defn. of $\Pi$}\\[1em] &= \frac{1}{k}\left(1-\frac{1}{k+1}\right)\tag{by $S(k)$, the ind. hyp.}\\[1em] &= \frac{1}{k}\left(\frac{k+1-1}{k+1}\right)\tag{common denom.}\\[1em] &= \frac{1}{k}\cdot\frac{k}{k+1}\tag{simplify}\\[1em] &= \frac{1}{k+1},\tag{simplify further} \end{align} one arrives at the right side of $S(k+1)$, thereby showing $S(k+1)$ is also true, completing the inductive step.

Conclusion: By mathematical induction, it is proved that for all $n\geq 2$, the statement $S(n)$ is true. $\Box$

Answer 5

This is an answer covering a somewhat more exotic proof. The claim is one I used in my answer at prove or disprove $H$ is a subgroup but I will expand on the details here and write it as nicely as possible.
For more about when induction can be done on these more exotic examples, see my blog post http://math.blogoverflow.com/2015/03/10/when-can-we-do-induction/.

Claim: Let $A\subseteq \mathbb{Z}$ be the smallest subset containing $1$ and closed under the operation $(n,m)\mapsto -(n+m)$.
Then $A = \{ n\in \mathbb{Z}\mid n\equiv 1\pmod{3}\}$.

Proof of claim: Let $B = \{ n\in \mathbb{Z}\mid n\equiv 1\pmod{3}\}$. First, we show that $A\subseteq B$ (this part does not use induction, but I will include it for completeness), which by definition means we need to show that $1\in B$ and that for any $n,m\in B$ we have $-(n+m)\in B$. The first part is trivially true, and for the second, we note that if $n\equiv m\equiv 1\pmod{3}$ then $n+m\equiv 2\pmod{3}$ and thus $-(m+n)\equiv -2 \equiv 1\pmod{3}$ which was the second part.

To show that $B\subseteq A$ we would like to proceed by induction, using the well-founded ordering "is closer to $0$" (more precisely, we say that $x\leq y$ if either $x = y$ or $|x| < |y|$). That this order is in fact well-founded I will leave as an exercise, since it is the actual induction proof that is important here.

For $n\in \mathbb{Z}$ we define the statement $P_n =$ "$n\in A$", and we would like to show that $P_n$ is true for all $n\in B$. Note that the assumption on $A$ now translates to $P_1$ and $P_m\wedge P_n\implies P_{-(m+n)}$.

Let $n\in B$ and assume that $P_m$ is true for all $m < n$ (in the order defined above).
We will first need to deal with the $n=1$ case, since there are no smaller elements in $B$. But $P_1$ is true by assumption, so this is clear.
We split into two cases, depending on whether $n$ is positive or negative.
If $n$ is negative, then $-n - 1 < n$ (in the order we are using). So by the induction hypothesis, $-n-1\in A$ since $-n-1\in B$. But $n = -((-n - 1) + 1)$, so since both $P_{-n-1}$ and $P_1$ are true, we also have $P_n$ (by the definition of $A$).

Now, if $n$ is positive, then $-n + 2 < n$, so by the induction hypothesis we have $-n + 2 \in A$. But we saw above that $-2\in A$ since $-2$ is negative and in $B$. So we have both $P_{-n+2}$ and $P_2$ and since $n = -((-n+2) + -2)$ this shows that we have $P_n$, which finishes the proof.