Mathematical Induction

Weak Induction [=Normal Induction] §

1. Base case

$$P(1)\text{ is true }$$

2. Inductive Hypothesis (IH)

$$\text{Assume }P(k)\text{ is true}$$

3. Inductive Step

$$P(k)\text{ is true }\Rightarrow P(k+1)\text{ is true}$$

Strong Induction §

1. Base cases

$$P(1)\dots P(n)\text{ is true}$$

2. Inductive Hypothesis (IH)

$$\text{Assume }P(k)\text{ is true}$$

3. Inductive Step

$$P(k)\text{ is true }\Rightarrow P(k+1)\text{ is true}$$