How to Write Proofs, 2

In the earlier post, "How to Write Proofs, A Quick Guide", I gave the example of a simple kind of result that one might come across (and should know how to prove) in intermediate logic:

(*) Suppose $S_0$ is $P\to Q$ and $S_{n+1}$ is $P\to S_n$. Show that, for all $n$, $S_n$ is equivalent to $P\to Q$.

The obvious proof uses induction (on $n$, as one says). We want to show that: every number $n\in \mathbb{N}$ has a certain property: namely, that the formula $S_n$ is equivalent to $P\to Q$. We can show this by induction. Induction says that if a property holds of $0$, and holds of $k+1$ whenever it holds of $k$, then it holds of all numbers. So, induction proofs proceed in three steps. First (the base step) show the property holds of $0$. Second (the induction step) show that, assuming it holds of $k$, it also holds of $k+1$. Finally, conclude that it holds of all numbers.

$\mathbf{\text{Base}}$. I.e., when $n=0$.
$S_0$ is $P\to Q$. This is obviously equivalent to $P\to Q$.

$\mathbf{\text{Induction Step}}$. I.e., from $k$ having the property, we want to show $k+1$ has it too.
So, suppose $S_k$ is equivalent to $P\to Q$. (This is the Induction Hypothesis.) We want to show that $S_{k+1}$ is equivalent to $P\to Q$ as well.
First, note that $S_{k+1}$ is defined to be $P\to S_k$. The Induction Hypothesis tells us that $S_k$ is equivalent to $P\to Q$. But we can use the simple lemma that "the substitution of equivalents leads to equivalents". So, we can conclude that $S_{k+1}$ is equivalent to $P\to (P\to Q)$. We only then need to show that this is equivalent $P\to Q$. I.e., that $P\to (P\to Q)\equiv P\to Q$. This can be done with a truth table. So, that completes the induction step.

From the Base Step and the Induction Step, we can conclude, using the Induction Principle, that for all $n$, $S_n$ is equivalent to $P\to Q$, as required. $\mathsf{Q}\mathsf{E}\mathsf{D}$.