Proof writing: how to write a clear induction proof?

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$

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.