Tao Analysis I - 2.2.5

Review: Weak & Strong Induction

Before we dive in, it is worth reviewing what standard "weak" and strong induction is. The following table summarises the difference (inspired by this).

Here $P(n)$ is a statement, or proposal, about a natural number $n$. For brevity, we've abused notation $P(m \leq n)$ to mean that $P(m)$ is true for all $m \leq n$. 

Weak Induction	Strong Induction
If $P(n_0)$ is true, And $P(n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$	If $P(n_0)$ is true, And $P(m \leq n) \implies P(n+1)$ Then $P(n)$ is true for all $n \geq n_0$

 

The only difference is that strong induction broadens the assumption that $P(n)$ is true to $P(m \leq n)$ is true. 

There is some confusion caused by the name "strong" because here it means broader assumptions, which to some ears (including mine), sounds like a weaker statement overall. To me, a theorem that makes fewer assumptions is stronger than an a theorem that requires lots of pre-requisites to be true.

The following visualises the difference between weak and strong induction.

 

Strong induction is used when $P(n)$ being true is insufficient to show $P(n+1)$ is also true. Let's look at an example of each.

Example: Weak Induction

This is the classic example used to illustrate standard, or weak, induction.

Aim: Prove that $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$

Inductive Hypothesis: $P(n) : 1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ is true.

Base Case:  LHS of $P(1)$ is 1. RHS of $P(1) = \frac{1(1+1)}{2}=1$.

Inductive Step: Consider $P(n+1)$. LHS is $1 + 2 + \ldots + n + (n+1)$. Using the inductive hypothesis, this is $\frac{n(n+1)}{2} + (n+1)$. Simple algebra leads to $\frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2}$. This is the RHS of $P(n+1)$. So $P(n) \implies P(n+1)$.

$P(1)$ being true, and $P(n) \implies P(n+1)$ means, by the principle of induction, $P(n)$ is true for all positive natural numbers $n$. $\square$

Note that we used the inductive hypothesis $P(n)$ to show $P(n+1)$ was true.

 

Example: Strong Induction

This is a classic example used to illustrate strong induction.

Aim: Prove that any natural number $n \geq 2$ is a product of primes. Note that a prime is considered to be a product of one prime.

Inductive Hypothesis: $P(n)$ : Every natural number less than or equal to $n$ is a product of primes.

Base Case: Consider $P(2)$. This states that 2 is a product of primes. We know 2 is a prime, and as such is a product of one prime. So $P(2)$ is true.

Inductive Step: Consider $m$ such that $2 \leq m \leq n$. We assume $P(m)$ is true. That is, we assume every natural number from 2 to $n$ is a product a primes. Now consider $P(n+1)$. Is $(n+1)$ a prime itself? There are two cases, yes and no. If yes, then $P(n+1)$ is true. If no, $(n+1)$ is not a prime, then it is a composite of 2 factors, $(n+1)=x \cdot y$ where $2 \leq x \leq n$ and $y$ are $2 \leq y \leq n$. The strong assumptions tell us that $x$ and $y$ are both products of one or more primes. Therefore $(n+1)$ is a product of primes too, and $P(n+1)$ is true in this second case.

With the base case $P(2)$ being true, and $P(2 \leq m \leq n) \implies P(n+1)$ being true, we have by strong induction shown that $P(n)$ is true for all positive natural numbers $n \geq 2$. 

Notice how we couldn't just use $P(n)$ to show $P(n+1)$. We needed $P(m)$ for $2 \leq m \leq n$.

Reference

This is a really clear summary of weak and strong induction with the classical examples.

• https://www.cs.cornell.edu/courses/cs2800/2011fa/Lectures/induction.pdf
  

 

Exercise 2.2.5

Prove Proposition 2.2.14. (Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_0 \leq m < n$; note that $Q(n)$ is vacuously true when $n \leq m_0$.)

Let's write out Proposition 2.2.14.

Proposition 2.2.14 (Strong principle of induction). Let $m_0$ be a natural number, and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m \geq m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0 \leq m' < m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m \geq m_0$.

This is probably the first exercise we encounter in Tao's analysis I which looks difficult (as opposed looking easy but turning out to be difficult). So it is worth taking a step back and thinking about what approach we'll be taking before diving in.

Approach. The question hint suggests we use weak induction to prove strong induction. We want to reformulate strong induction in terms of weak induction. That is, we're solving a more challenging problem by reformulating into a more familiar problem.

Let's rewrite our previous table in terms of the variables given by the question. Note the different endpoints for the range of $m'$.

Weak Induction	Strong Induction
If $Q(n_0)$ is true, And $Q(n) \implies Q(n+1)$ Then $Q(n)$ is true for all $n \geq n_0$	If $P(m_0)$ is true, And $P(m_0 \leq m' < m) \implies P(m)$ Then $P(m)$ is true for all $m \geq m_0$

Before we dive in, let's be clear about what we need to prove, and what we can assume to be true:

• We need to find a base case for $Q(n_0)$ which is true.
• We need to show that if $Q(n)$ is true, then so is $Q(n+1)$.
  
• We can assume $P(m_0)$ is true for the purposes of proving strong induction.
• We can assume  $P(m_0 \leq m' < m) \implies P(m)$ is true for the purposes of proving strong induction.
  

Let's follow the standard template for weak induction over $n$, here using $Q(n)$. 

Inductive Hypothesis: $Q(n)$ is true.  

Let's write what this means in terms of $P(m')$.

$$Q(n) : P(m_0 \leq m' < n)$$

Inductive Step: $Q(n) \implies Q(n+1)$.

Since $P(m_0 \leq m' < n) \implies P(n)$, we have $P(m_0 \leq m' \leq n)$.

This means $Q(n+1)$ is true, because

$$Q(n+1) : P(m_0 \leq m' < n+1) = P(m_0 \leq m' \leq n)$$

So $Q(n) \implies Q(n+1)$.

Base Case: Consider $Q(m_0)$.

$$Q(m_0) : P(m_0 \leq m' < m_0)$$

This is vacuously true since no $m'$ satisfies $m_0 \leq m' < m_0$. 

By weak induction (Axiom 2.5), having shown the base case $Q(m_0)$ to be (vacuously) true, and that $Q(n) \implies Q(n+1)$, we can conclude $Q(n)$ is true for all $n \geq m_0$. 

What does this mean? Referring back to the definition of $Q(n)$,

$$Q(n) : P(m_0 \leq m' < n)$$

$Q(n)$ is true for all $n \geq m_0$ means

$$Q(n \geq m_0) : P(m_0 \leq m')$$

So we have shown $P(m)$ is true for all natural numbers $m \geq m_0$. $\square$