I will answer this question with four
typical examples, all different in nature:
Example 1:
Prove by induction that $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$.
For proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:
Step 1: Basis Case: For $n=1 \implies n^3-n+3= 1^3-1+3=3$ which is divisible by $3$. So statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that $n^3-n+3=\color{blue}{(k^3-k+3)}=\color{blue}{3p} \tag{1}$ Where $p,k \in \mathbb{N^+}$.
Step 3: Prove Statement holds for $n=k+1$ such that $$n^3-n+3=(k+1)^3-(k+1)+3$$
$$=k^3+3k^2+3k+1-k-1+3=3k^2+3k+\color{blue}{(k^3-k+3)}= 3(k^2+k)+\color{blue}{3p}=\color{#180}{3}(k^2+k+p)$$ using our inductive assumption $(1)$ the resulting expression clearly is divisible by $3$.
Hence $n^3-n+3$ is divisible by $3$ $\forall \space n \in \mathbb{N^+}$
QED.
(QED is an abbreviation of the Latin words "Quod Erat Demonstrandum" which loosely translated means "that which was to be demonstrated". It is usually placed at the end of a mathematical proof to indicate that the proof is complete). Alternatively, you can use $\fbox{}$
Example 2:
Use trigonometric identities and induction to prove that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n} =
\left(\begin{array}{cc}
\cos (n \theta) & -\sin (n\theta)\\
\sin (n \theta) & \cos (n \theta)
\end{array} \right)$
As before, for proof by induction; these are the $\color{red}{\mathrm{three}}$ steps to carry out:
Step 1: Basis Case: For $n=1 \implies$ LHS
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{1}$
$=\left(\begin{array}{cc}
\cos (1 \theta) & -\sin (1\theta)\\
\sin (1 \theta) & \cos (1 \theta)
\end{array} \right)$
$=\left(\begin{array}{cc}
\cos (\theta) & -\sin (\theta)\\
\sin ( \theta) & \cos ( \theta)
\end{array} \right)=$ RHS. So statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$ such that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k}$
$=\left(\begin{array}{cc}
\cos (k \theta) & -\sin (k\theta)\\
\sin (k \theta) & \cos (k \theta)
\end{array} \right)\tag{1}$
Step 3: Prove Statement holds for $n=k+1$ such that
$\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{n}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k+1}$
$=\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{k}$ $\times
\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)^{1}$
$=\left(\begin{array}{cc}
\cos (k \theta) & -\sin (k\theta)\\
\sin (k \theta) & \cos (k \theta)
\end{array} \right)
\times
\left(\begin{array}{cc}
\cos \theta & -\sin \theta \\
\sin \theta & \cos \theta
\end{array} \right)$
[using our inductive assumption $(1)$]
$=\left(\begin{array}{cc}
\cos\theta\cos (k \theta)-\sin\theta \sin(k\theta) & -\left(\sin \theta\cos (k \theta)+\sin (k \theta)\cos \theta\right)\\
\cos\theta\sin (k \theta)+\sin\theta \cos(k\theta) & \cos\theta\cos (k \theta)-\sin\theta \sin(k\theta)
\end{array} \right)$
$=\color{blue}{\left(\begin{array}{cc}
\cos (\theta(k+1)) & -\sin (\theta(k+1))\\
\sin (\theta(k+1)) & \cos(\theta(k+1))
\end{array} \right)}$
Where in the last step I used the fact that $$\cos(A \mp B)=\cos A \cos B \pm \sin A \sin B$$ and $$\sin(A \pm B)=\sin A \cos B \pm \cos A \sin B$$ and $\color{blue}{\mathrm{this}}$ is the same result if $n=k+1$ is substituted into the RHS of your original disposition.
Hence statement is true for all $n \in \mathbb{N}.$
QED.
Example 3:
Prove by induction that $3^{(3n+4)} + 7^{(2n+1)}$ is divisible by $11$ for all natural numbers $n$:
Step 1: Basis Case: for $n=1$: $P(1)= 3^{(3(1)+4)} + 7^{(2(1)+1)} = 2530$, which is divisible by $11$ so statement holds for $n=1$.
Step 2: Inductive Assumption: Assume statement is true for $n=k$: $P(k) =3^{(3k+4)} + 7^{(2k+1)} = 11a \implies 3^{3k+4} = \color{blue}{11a - 7^{2k+1}}$, where $a \in \mathbb{N}$
Step 3: Prove Statement holds for $n=k+1$:
$P(k+1)= 3^{3k+7} + 7^{2k+3} = 27 \cdot 3^{3k+4} + 49\cdot 7^{2k+1}\tag{1}$
Using the inductive assumption shown in $\color{blue}{\mathrm{blue}}$, $(1)$ becomes:
$27(\color{blue}{11a - 7^{2k+1}})+49\cdot 7^{2k+1}=27\cdot 11a -27\cdot 7^{2k+1}+ 49\cdot 7^{2k+1}=27\cdot 11a +2\cdot 11\cdot 7^{2k+1}=\color{red}{11}(27a+2\cdot 7^{2k+1})$
Hence $3^{3n+4} + 7^{2n+1}$ is a multiple of $\color{red}{11} \space\forall \space n\in \mathbb{N}$
QED.
Example 4:
Prove by induction that $$\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} \quad \forall \space n \in \mathbb{N}$$
Step 1: Basis Case: For $i=1$: $$\sum^{i=k}_{i=1} i^2=\frac{1(1+1)(2\times 1+1)}{6}= \frac{2\times 3}{6}=1$$ So statement holds for $i=1$.
Step 2: Inductive Assumption: Assume statement is true for $i=k$:
$$\sum^{i=k}_{i=1} i^2=\frac{k(k+1)(2k+1)}{6} $$
Step 3: Prove Statement holds for $i=k+1$. You need to prove that for $i=k+1$: $$\sum^{i=k+1}_{i=1} i^2=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}$$
To do this you cannot use: $$\sum^{i=k}_{i=n} i^2=\color{red}{\frac{n(n+1)(2n+1)}{6}} $$ as this is what you are trying to prove.
So what you do instead is notice that:
$$\sum^{i=k+1}_{i=1} i^2= \underbrace{\frac{k(k+1)(2k+1)}{6}}_{\text{sum of k terms}} + \underbrace{(k+1)^2}_{\text{(k+1)th term}}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{k(k+1)(2k+1)}{6}+\frac{6(k+1)^2}{6}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)\left(k(2k+1)+6(k+1)\right)}{6}$$
$$\sum^{i=k+1}_{i=1} i^2= \frac{(k+1)(2k^2+\color{green}{7k}+6)}{6}=\frac{(k+1)(2k^2+\color{green}{4k+3k}+6)}{6}=\frac{(k+1)\left(2k(k+2)+3(k+2)\right)}{6}=\color{blue}{\frac{(k+1)(k+2)(2k+3)}{6}}\quad \forall \space k,n \in \mathbb{N} \quad\fbox{}$$
Which is the relation we set out to prove. So the method is to substitute $i=k+1$ into the formula you are trying to prove and then use the inductive assumption to recover the $\color{blue}{\mathrm{blue}}$ equation at the end.
Observe that in the part marked $\color{green}{\mathrm{green}}$ $7k$ has simply been rewritten as $4k+3k$. From then on you simply take out common factors.
Note that this method is only valid when you have two numbers whose product is $12$ and sum is $7$.
Or, put in another way for the general quadratic $ax^2 +bx +c$, this inspection method is only valid iff you can find two numbers whose product is $ac$ and sum is $b$.
Main suggestion
Instead of
We want to show $\def\p{\phi}\def\q{\psi}\def\s{\vDash_{\tiny\text{PL}}}\def\ns{\nvDash_{\tiny\text{PL}}}\p_1,\,\p_2,\,\ldots,\,\p_n\s\q$ iff $\s\p_n\to(\p_{n-1}\to(\cdots\to(\p_1\to\q)\cdots))$
try it like this:
We want to show that $$\def\p{\phi}\def\q{\psi}\def\s{\vDash_{\tiny\text{PL}}}\def\ns{\nvDash_{\tiny\text{PL}}}\p_1,\,\p_2,\,\ldots,\,\p_n\s\q \tag{1}$$ if and only if
$$\s\p_n\to(\p_{n-1}\to(\cdots\to(\p_1\to\q)\cdots)).\tag{2}$$
After that, instead of repeating the long formulas every time, just call them $(1)$ and $(2)$:
For reductio, suppose it's not the case that $(2)\implies (1)$. Then there must exist an $\mathscr I$ such that $(2)$ holds but $(1)$ does not.
Lesser suggestions
Abbreviate $$\phi_n\to(\phi_{n-1}\to(\cdots\to(\phi_1\to\q)\cdots))$$ as $$\Phi_n.$$ (Don't use $Q$. Why would you use $Q$?)
Instead of $$V_\mathscr{I}({p_k\to(\p_{k-1}\to(\cdots\to(\p_1\to\q)\cdots))})=0$$ you can now write $$V_\mathscr{I}({p_k\to\Phi_{k-1}})=0$$ and the reader won't miss that the first variable is a $p$ and not a $\phi$.
You said abbreviating seems “more confusing than helpful”. It's not.
Abbreviate $\phi_1,\phi_2,\ldots,\phi_n$ as $\vec\phi$.
Abbreviate $$V_\mathscr{I}(\phi_n)=V_\mathscr{I}(\phi_{n-1})=\cdots=V_\mathscr{I}(\phi_1)=1$$ as $$V_\mathscr{I}(\phi_i) = 1\quad (i=1\ldots n)$$ or perhaps $$V_\mathscr{I}(\phi_{1\ldots n}) = 1.$$
You're abbreviating the wrong things. You don't need to abbreviate “if and only if” as “iff”, or “Lemma 1” as “L1”. The goal here is not to remove all the normal English from your proof. These abbreviations are more confusing than helpful.
Don't make the reader compare two long formulas to make sure they are the same, or to wonder why they are not. Design your notation to highlight the differences between similar formulas.
Notation, like language, is flexible. There are no rules; you are allowed to make things up. $\vec\phi$ is not really a vector. It doesn't matter. You can explain it briefly: “We will abbreviate $\phi_1,\phi_2,\ldots,\phi_n$ as $\vec\phi$.” Nobody will be confused or forget what it means. My suggestion $V_\mathscr{I}(\phi_{1\ldots n})$ is not standard. It doesn't matter; the meaning is clear.
Orthogonal suggestions
You're not using TeX correctly. You don't need to keep repeating \def
s. Once you \def
a new control sequence, the definition remains in force until the end of the group, or the document. Define the important macros once, at the beginning of the file, or in an \include
d file.
Define better macros. The structure of the macros should follow the syntactic structure of your formulas. Instead of typing out
\def\aa{\p_1,\,\p_2,\,\ldots,\,\p_n\s\q}
\def\ab{\p_1,\,\p_2,\,\ldots,\,\p_n\ns\q}
\def\ba{\s\p_n\to(\p_{n-1}\to(\cdots\to(\p_1\to\q)\cdots))}
\def\bb{\ns\p_n\to(\p_{n-1}\to(\cdots\to(\p_1\to\q)\cdots))
try it this way:
\def\ps{\p_1,\,\p_2,\,\ldots,\,\p_n}
\def\aa{\ps\s\psi}
\def\ab{\ps\ns\psi}
\def\pformn{\p_n\to(\p_{n-1}\to(\cdots\to(\p_1\to\psi)\cdots))}
% now you don't need \ba or \bb, just use \s\pformn and \ns\pformn
Best Answer
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: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$.
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.
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."
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.
Inductive step: Write out the words "Inductive step:"
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.
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.
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.
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."
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$