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

Proof by Finite Induction

The proof will proceed by the Principle of 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 $k \in S$ where $k \ge 1$, then it follows that $k + 1 \in S$.

This is the induction hypothesis:

$\text {expression for $k$}$

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 $k \in S \implies k + 1 \in S$ and the result follows by the Principle of Finite Induction:

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