## Principle of mathematical induction

Here's the statement of the principle of mathematical induction:

For each positive integer \( n \) let \( P(n) \) be a statement. If

- \( P(1) \) is true, and
- \( \forall k \in \natural, P(k) \Rightarrow P(k+1) \)

then, \( \forall n \in \natural, P(n) \) is true.

A proof using this principle is known as an **induction proof** or a **proof by induction**.

The first step, the verification of the truth of \( P(1) \) is known as the **base step, basis step** or the **anchor** of the induction.
The implication \( P(k) \Rightarrow P(k+1) \) for arbitrary positive integer \( k \) is known as the **inductive (or induction) hypothesis**.
Establishing the truth of this implication is called the **inductive step ** of the induction proof.

Note that more generally, the principle of mathematical induction is also applied to proofs of the form "For every integer \( n \ge m, P(n) \)" by starting with the base step verifying the truth of \( P(m) \).

#### Example

**Prove:** \( \forall n \in \natural, \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)

**Proof:**

Let \( f(n) = \sum_{i=1}^n \) and \( g(n) = \frac{n(n+1)}{2} \).

We need to show that \( f(n) = g(n), \forall n \in \natural \).

As the base step, observe that

$$ f(1) = \frac{1(1+1)}{2} = 1 $$

The induction hypothesis is then suppose \( f(k) = \frac{k(k+1)}{2} \). Thus,

\begin{align}
f(k+1) = &~ f(k) + (k+1) \\\\
= &~ \frac{k(k+1)}{2} + (k+1) \\\\
= &~ \frac{k^2 + k + 2k + 2}{2} \\\\
= &~ \frac{(k+1)(k+2)}{2}
\end{align}

Thus, we have shown that if \( f(k) = \frac{k(k+1)}{2} \) for some \( k \in \natural \), then \( f(k+1) = \frac{(k+1)(k+2)}{2} \), thereby completing the induction step.
Hence, \( \forall n \in \natural, f(n) = \frac{n(n+1)}{2} \).