User:Prime.mover/Proof Structures/Proof by Finite Induction
Jump to navigation
Jump to search
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}: ...$