2 Strong Induction

Let $P$ be a proposition (predicate) being proven. Let $a \le b$ both be integers. Then, strong induction states the following:

$(\forall i \in I: (a \le i \le b) \rightarrow P(i)), (\forall k \in I, (\forall... ...w P(i))) \rightarrow P(k)) \vdash (\forall n \in I: (n \ge a) \rightarrow P(n))$

Okay, that's pretty cryptic, even for computer scientists. Let us review step by step.

First of all, induction is a form of inference. It has a general form of $A, B \vdash C$, which says given that $A$ and $B$ are true, then we can conclude that $C$ is true. In this case, $A$ and $B$ are somewhat complicated propositions themselves.

$A$ states that $\forall i \in I: (a \le i \le b) \rightarrow P(i)$. This means that we have at least one base case, but possibly many bases cases. The base cases must be contiguous. The truth of each base case is usually either by definition, or proven by techniques other than induction (such as direct proof or proof by contradiction).

$B$ states that $\forall k \in I, (\forall i \in I: (a \le i < k \rightarrow P(i))) \rightarrow P(k)$. This is the induction step. This requires a little bit more explanation.

First of all, $a \le i < k \rightarrow P(i)$ is the condition of a conditional proposition (although it is a conditional proposition by itself). This proposition states that $P(i)$ is true for all $i$ such that $a \le i < k$. The truth of this proposition is assumed for the next step.

The difficult part is to prove that $a \le i < k \rightarrow P(i)$ leads to $P(k)$. In other words, assuming that $P(a), P(a+1),\cdots P(b), P(b+1),\cdots P(k-1)$, can we prove $P(k)$?

If we can, indeed, prove that $P(a), P(a+1),\cdots P(b), P(b+1),\cdots P(k-1)$ does lead to $P(k)$, and that we have base cases $P(a),\cdots P(b)$, then we can conclude that $P(n)$ is true for all $a \le n$.

No explanation of induction is complete, or even sane, without examples.