User:Prime.mover/Proof Structures/Proof by Complete Finite Induction

Proof by Complete Finite Induction

The proof will proceed by the Principle of Complete Finite Induction on $\Z_{>0}$.

Let $S$ be the set defined as:

$S := \set {n \in \Z_{>0}: ...}$

That is, $S$ is to be the set of all $n$ such that:

$...$

Basis for the Induction

We have that:

(proof that $1 \in S$)

So $1 \in S$.

This is the basis for the induction.

Induction Hypothesis

It is to be shown that if $j \in S$ for all $j$ such that $0 \le j \le k$, then it follows that $k + 1 \in S$.

This is the induction hypothesis:

$\forall j \in \Z_{>0}: 1 \le j \le k: \text {expression for $j$}$

It is to be demonstrated that it follows that:

$\text {expression for $k + 1$}$

Induction Step

This is the induction step:

\(\ds \)

\(=\)

\(\ds \)

\(\ds \leadsto \ \ \)

\(\ds \)

\(=\)

\(\ds \)

So $\forall j \in S: 0 \le j \le k: j \in S \implies k + 1 \in S$ and the result follows by the Principle of Complete Finite Induction:

$\forall n \in \Z_{>0}: ...$