Proof by Mathematical Induction
Mathematical induction is a method of proof used to establish that a statement is true for all natural numbers. The main idea is that you assume that the statement is true for some natural number. Then you show, that if it is true for that natural number, then it is true for the next. Hence, if you find it is true for some number, then this means it is true for the next, hence it is true for the next, and so on, proving for it is true for all numbers greater.
Steps
It consists of a few main steps (and one extra but important step for the examinations):
- Call your statement $P(n)$. For example, "$P(n)$: $n(n+1)(n+2)$ is divisible by $6$ for all numbers $n\in\mathbb{N}$."
- Base case: Prove the statement is true for the smallest value (usually $n = 1$ or $n = 0$, but there can be others, so make sure to check what the smallest possible value is). Call this $P(1)$ or $P(0)$ (or whatever number you're using as the base case).
- Inductive hypothesis: Assume $P(k)$ holds for some number $k\in\mathbb{N}$ - i.e. the statement is true for some arbitrary natural number $k$. Let this $k$ be bigger than or equal to the number you used in your base step.
- Inductive step: Hence, now prove $P(k+1)$ holds if $P(k)$ holds – i.e. the statement is true for $k+1$ if it is true for $k$. Make sure to use your inductive hypothesis somewhere – this is what differentiates proof by induction from proof by deduction.
- (Extra but important) Conclusion: Make sure to give a conclusion that $P(k+1)$ holds if $P(k)$ holds for $k\in\mathbb{N}$, and $P(\text{base case})$ holds, therefore $P(n)$ holds for all $n \geq \text{base case}$.
Let's prove that the sum of the first $n$ positive integers is given by the formula:
$$P(n): S_n = \frac{n(n+1)}{2} $$
Base case ($n = 1$): $P(1): S_1 = 1 = \frac{1(1+1)}{2} = 1$, so $P(n)$ holds for $n = 1$.
Inductive hypothesis: Assume $P(k)$ holds for some number $k\in\mathbb{N}$ where $k\geq1$, i.e., $S_k = \frac{k(k+1)}{2}$
Inductive step:
$S_{k+1} = S_k + (k+1)$
$= \frac{k(k+1)}{2} + (k+1)$
$= \frac{k(k+1) + 2(k+1)}{2}$
$= \frac{(k+1)(k+2)}{2}$
This is exactly the formula for $n = k + 1$, thus $P(k+1)$ holds if $P(k)$ holds.
Conclusion: $P(k+1)$ holds if $P(k)$ holds, and $P(1)$ holds. Thus, $P(n)$ holds for all $n\in\mathbb{N}$.
Exam techniqueIn exams, follow this exact structure, including the notation $P(n)$. Don't add or remove anything – this could put you at risk of being docked marks.
