EQ 8 Proof By Induction

(1) Axiom: Mathematical Induction Over \( \mathcal{N} \). Form 1

( \( \forall \) n:\( \mathcal{N} \) |: ( \( \forall \)i | 0 \( \leq \) i \( \lt \) n: \(P_i\)) \( \Rightarrow \) \(P_n\) ) \( \Rightarrow\) ( \( \forall \) n : \( \mathcal{N} \) : \(P_n\))

used to prove Universal Quantification By Induction


(2) Theorem: Mathematical Induction Over \( \mathcal{N} \). Form 2

( \( \forall \) n:\( \mathcal{N} \) |: ( \( \forall \)i | 0 \( \leq \) i \( \lt \) n: \(P_i\)) \( \Rightarrow \) \(P_n\) ) \( \equiv\) ( \( \forall \) n : \( \mathcal{N} \) : \(P_n\))

used to prove properties of Induction

(3) Theorem: Mathematical Induction Over \( \mathcal{N} \). Form 3

\( P_0\) \( \wedge \) ( \( \forall \) n:\( \mathcal{N} \) |: ( \( \forall \)i | 0 \( \leq \) i \( \leq \) n: \( P_i\) ) \( \Rightarrow \) \( P_{n+1} \) ) \( \Rightarrow\) ( \( \forall \) n : \( \mathcal{N} \) : \(P_n\))

restatement of (1) used for inductive proofs

(4) Parts of Mathematical Induction axiom

\( P_0\) is the base case

( \( \forall \) n:\( \mathcal{N} \) |: ( \( \forall \)i | 0 \( \leq \) i \( \leq \) n: \( P_i\) ) \( \Rightarrow \) \( P_{n+1} \) ) \( \Rightarrow\) ( \( \forall \) n : \( \mathcal{N} \) : \(P_n\)) is the inductive case

( \( \forall \) n:\( \mathcal{N} \) |: ( \( \forall \)i | 0 \( \leq \) i \( \leq \) n: \( P_i\) ) \( \Rightarrow \) \( P_{n+1} \) ) is the inductive hypothesis

(5) Normal Proof Method

(1) Prove Base Case. \( P_0 \)

(2) Assume arbitrary n \( \ge \) 0

(3) Assume Inductive Case ( \( \forall \)i | 0 \( \leq \) i \( \leq \) n: \( P_i\) )

(4) Prove \( P_{n+1} \)


(6) Induction starting at other integers

Let a sequence of integers start at \( n_0 \) Then Inductive Theorem is

\( P_{n_0}\) \( \wedge \) ( \( \forall \) n:\(n_0 \leq n \)|: ( \( \forall \)i | \(n_0 \leq \) i \( \leq \) n: \( P_i\) ) \( \Rightarrow \) \( P_{n+1} \) ) \( \Rightarrow\) ( \( \forall \) n : \(n_0 \leq n \) : \(P_n\))