> See also: > - [[Summations]] > - [[Recursion]] # Mathematical Induction The technique of mathematical induction can be applied when there is an open statement of the form: $\forall n \in \mathbb{Z}^+ p(n)$ Common types of induction problems: - Summation Equality - Summation Inequality - Divisibility - Matrix - Other - Strong Induction It’s called **the induction principle** and not the induction theorem for a reason. - Induction is an observed pattern and is such a fundamental numeric principle that it’s often difficult to actually prove as a formal theorem (similar to pigeonhole) ## General Process 1) **Base Case** $n=1$ is often chosen as it is the first positive integer and is a suitable foundation (base) for the rest of the proof to rely on. Prove the base case to lay the foundation 2) **Induction Hypothesis** 3) **Inductive Step** ## Strong Induction Sometimes the typical inductive step of proving $f(k)\implies f(k+1)$ is not sufficient. Strong induction goes a step further by laying a "stronger foundation" **Strong induction** almost always requires *multiple base cases* - You may not know how many base cases are required until you have completed most of the problem "A stronger foundation (base case) leads to stronger induction" The inductive hypothesis of a strong induction proof must be written with much more care.