# The Principle of Weak Mathematical Induction

We will now look at a very important proof technique known as **weak mathematical induction**.

Principle of Weak Mathematical Induction: Let $n_0 \in \mathbb{N}$ and let $P(n)$ be a statement relevant to all natural numbers $n ≥ n_0$. If the statement $P(n_0)$ is true and the truth of $P(k)$ implies the truth of $P(k+1)$, then $P(n)$ is true for all $n ≥ n_0$. |

To do a proof my weak mathematical induction, we will first formally start the proof with a little introduction stating our statement $P(n)$. We will then proceed to show that $P(n_0)$ is true ($n_0$ is our starting point. Usually we'll start at $n_0 = 1$). Afterwards, we will assume that $P(k)$ is true for any natural number $k ≥ n_0$ and then show that it implies the truth of $P(k + 1)$ by using the assumed truth of $P(k)$.

We will now look at some examples of weak mathematical induction.

## Example 1

**Show by weak mathematical induction that $1 + 2 + ... + n = \frac{n(n+1)}{2}$ for every natural number $n ≥ 1$.**

Let $n ≥ 1$. We want to show that the statement $P(n): 1 + 2 + ... + n = \frac{n(n+1)}{2}$ is true. We will first show that $P(1)$ is true.

When $n = 1$ note that the lefthand side of our equation is equal to $1$. Furthermore, the righthand side of our equation is equal to $\frac{1(2)}{2} = 1$ and hence, $P(1)$ is true.

Now suppose that for some $k ≥ 1$, $P(k): 1 + 2 + ... + k = \frac{k(k+1)}{2}$ is true. We want to show that the truth of $P(k)$ implies the truth of $P(k+1): 1 + 2 + ... + k + (k+1) = \frac{(k+1)(k+2)}{2}$. We start with the lefthand side of this statement and use the truth of $P(k)$, also known as our **induction hypothesis** in deriving the truth of $P(k+1)$ (the use of the induction hypothesis is denoted below with the equality symbol $\overset{IH} =$).

Therefore the truth of $P(k)$ implies the truth of $P(k+1)$ and so for every $n ≥ 1$, $P(n)$ is true. $\blacksquare$

## Example 2

**Show by weak mathematical induction that $1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$ for every natural number $n ≥ 1$.**

Let $n ≥ 1$. We want to show that the statement $P(n): 1^2 + 2^2 + ... + n^2 = \frac{n(n+1)(2n+1)}{6}$ is true. We will first show that $P(1)$ is true.

When $n = 1$, notice that the lefthand side of this equation is equal to $1$. Similarly, the righthand side of the equation is equal to $\frac{1(2)(3)}{6} = 1$. Therefore $P(1)$ is true.

Now suppose that for some arbitrary $k ≥ 1$, $P(k): 1^2 + 2^2 + ... + k^2 = \frac{k(k+1)(2k+1)}{6}$ is true. We want to show that $P(k)$ implies the truth of the statement $P(k+1) = 1^2 + 2^2 + ... + k^2 + (k+1)^2 = \frac{(k+1)(k+2)(2k + 3)}{6}$. We start with the lefthand side of this equation:

(2)Therefore the truth of $P(k)$ implies the truth of $P(k+1)$ and so for every $n ≥ 1$, $P(n)$ is true. $\blacksquare$

## Example 3

**Show by weak mathematical induction that $1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{4n^3 - n}{3}$ for every natural number $n ≥ 1$.**

Let $n ≥ 1$. We want to show that statement $P(n): 1^2 + 3^2 + 5^2 + ... + (2n - 1)^2 = \frac{4n^3 - n}{3}$ is true. We will first show that $P(1)$ is true.

When $n = 1$, notice that the lefthand side of the equation is also equal to $1$. Furthermore the righthand side of this equation is equal to $\frac{4(1) - 1}{3} = 1$. Therefore $P(1)$ is true.

Now suppose that for some arbitrary $k ≥ 1$, $P(k) = 1^2 + 3^2 + 5^2 + ... + (2k - 1)^2 = \frac{4k^3 - k}{3}$ is true. We want to show that $P(k)$ implies the truth of $P(k+1): 1^2 + 3^2 + 5^2 + ... + (2k - 1)^2 + (2(k+1) - 1)^2 = \frac{4(k+1)^3 - (k+1)}{3}$. We will start with the lefthand side of this equation.

(3)We're now going to work backwards since factoring a cubic polynomial is not necessarily the easiest thing ever. Note that:

(4)Therefore $4k^3 + 12k^2 + 11k + 3 = 4(k+1)^3 - (k+1)$ and so:

(5)Therefore the truth of $P(k)$ implies the truth of $P(k+1)$ and so for every $n ≥ 1$, $P(n)$ is true. $\blacksquare$