## Tuesday, October 4, 2011

### 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$$)