21
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ You might want to clarify the example with $\mathbb{Q}$ in the question, as it only works for positive rationals (the rationals are not well-founded using $p+q$). $\endgroup$ – Tobias Kildetoft Apr 27 '15 at 9:23
  • $\begingroup$ For a slightly exotic example that should be easy to understand if written in more detail, see my answer here math.stackexchange.com/questions/1118486/… $\endgroup$ – Tobias Kildetoft Apr 27 '15 at 9:36
  • $\begingroup$ Not sure. I might have some time tomorrow, but we will have to see. $\endgroup$ – Tobias Kildetoft Apr 27 '15 at 9:57
  • $\begingroup$ See the answer, Frequent Induction Questions, at meta.math.stackexchange.com/questions/1868/… $\endgroup$ – Gerry Myerson Apr 27 '15 at 13:21
  • $\begingroup$ I am somewhat confused by your question--do you mean, more or less, a sort of template almost for writing nice, polished induction proofs? Otherwise, Gerry's meta link seems to answer your question. $\endgroup$ – Daniel W. Farlow Apr 27 '15 at 15:42
25
$\begingroup$

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

enter image description here

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$

$\endgroup$
  • 1
    $\begingroup$ @AlexandreHalm I'll try to respond point by point: 1) There is a reason why my answer is as long as it is, but I would not characterize it as verbose. Each section, four in total, is clearly demarcated so as to facilitate ease of reading, 2) A very long answer may deter some readers, but if these readers are unwilling to read something that is intended solely to help them, then that is their own loss, and I have no problem with them skipping over my answer, 3) Quite a bit of it I wrote myself--the real adaptation was the template itself and many of the remarks concerning $\endgroup$ – Daniel W. Farlow Apr 28 '15 at 13:12
  • 1
    $\begingroup$ (cont’d) the rationale for this template, 4) Concerning the picture: no one is as opposed as me in regards to unnecessarily pasting pictures, but this is not such a case. The picture is actually a screenshot of something I typeset (not from an external source) using ${\rm\LaTeX}$, but the full richness of ${\rm\TeX}$ is not available on MSE (I used framebox, parbox, and a host of other ${\rm\LaTeX}$ features not available here). There are two other benefits to posting a picture here: readers who find the template helpful can right-click to Save Image As… instead of having to $\endgroup$ – Daniel W. Farlow Apr 28 '15 at 13:12
  • 1
    $\begingroup$ (cont’d) come back to my answer every single time they want access to the template. Pictures in general, of course, are discouraged on MSE, but there are occasions where either ease of access or difficulty of typography make posting a picture encouraged, and this answer suits both occasions in my opinion. For example, how would you like to typeset this other [induction answer]( math.stackexchange.com/questions/1115105/…)? $\endgroup$ – Daniel W. Farlow Apr 28 '15 at 13:13
  • 1
    $\begingroup$ Lastly, my intention of providing such a comprehensive answer was not at all for me but for other users (novice or otherwise) to have for future reference. Apparently, at this point, I have answered $33$ induction problems over the past [$30$ days]( math.stackexchange.com/tags/induction/topusers), and I have been asked questions multiple times for which linking to this template would have been very helpful. Now I can do that. For anyone who truly wants to know how to write a nice induction proof, I don’t think the length of my answer will be a problem. $\endgroup$ – Daniel W. Farlow Apr 28 '15 at 13:13
  • 1
    $\begingroup$ @NewBornMATH That is strange timing then--OP is still active on MSE, but you may have the most success by looking at the induction tag on this site. Or you could always check out the book on induction by Gunderson. That book has all you could want concerning induction. $\endgroup$ – Daniel W. Farlow Mar 24 '19 at 20:52
5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.