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} =$).

(1)

\begin{align} LHS_{P(k+1)} : \underbrace{1 + 2 + ... + k} + (k + 1) \\ \overset{IH} = \underbrace{\frac{k(k+1)}{2}} + (k + 1) \\ = \frac{k(k+1) + 2(k+1)}{2} \\ = \frac{(k+1)(k + 2)}{2} \end{align}

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)

\begin{align} LHS_{P(k+1)} : \underbrace{1^2 + 2^2 + ... + k^2} + (k+1)^2 \\ \overset{IH} = \frac{k(k+1)(2k+1)}{6} + (k+1)^2 \\ = \frac{k(k+1)(2k+1) + 6(k+1)^2}{6} \\ = \frac{(k+1)[k(2k+1) + 6(k+1)]}{6} \\ = \frac{(k+1)[2k^2 + k + 6k + 6]}{6} \\ = \frac{(k+1)[2k^2 + 7k + 6]}{6} \\ = \frac{(k+1)[2k^2 + 4k + 3k + 6]}{6} \\ = \frac{(k+1)(k+2)(2k+3)}{6} \end{align}

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)

\begin{align} LHS_{P(k+1)}: \underbrace{1^2 + 3^2 + 5^2 + ... + (2k - 1)^2} + (2(k+1) - 1)^2 \\ \overset{IH} = \frac{4k^3 - k}{3} + (2(k+1) -1)^2 \\ = \frac{4k^3 - k + 3(2(k+1) - 1)^2}{3} \\ = \frac{4k^3 - k + 3(2k+1)^2}{3} \\ = \frac{4k^3 - k + 3(4k^2 + 4k + 1)}{3} \\ = \frac{4k^3 - k + 12k^2 + 12k + 3}{3} \\ = \frac{4k^3 + 12k^2 + 11k + 3}{3} \\ \end{align}

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

(4)

\begin{align} \quad \quad 4(k+1)^3 - (k+1) = 4(k+1)(k^2 + 2k + 1) - (k +1) = 4(k^3 + 2k^2 + k + k^2 + 2k + 1) - (k+1) \\ \quad \quad = 4(k^3 + 3k^2 + 3k + 1) - (k +1) = 4k^3 + 12k^2 + 12k + 4 - k - 1 = 4k^3 + 12k^2 + 11k + 3 \end{align}

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

(5)

\begin{align} LHS_{P(k+1)}: = \frac{4k^3 + 12k^2 + 11k + 3}{3} \\ = \frac{4(k+1)^3 - (k+1)}{3} \end{align}

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