Tao Analysis I - 2.2.7

Exercise 2.2.7

Let $n$ be a natural number, and let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m)$ is true, $P(m++)$ is true. Show that if $P(n)$ is true, then $P(m)$ is true for all $m \geq n$. (This principle is sometimes referred to as the principle of induction starting from the base case $n$.)

This looks easier than the last two exercises - let's hope it is!

 

Approach

The first thing to notice is that this scenario is very similar to the standard induction scenario, with the only difference beting that the variable is shifted up, from $m \geq 0$ to $m \geq n)$. This suggests we can reformulate the problem into the standard scenario by variable substitution.

 

Proof

Let's set

$$q = m-n$$

Here $n$ is fixed, and $m$ is free, and both are natural numbers.

If we can show that

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

Then by the induction principle Axiom 2.5, we can say $P(q)$ is true for all natural numbers $q$.

Let's first consider $P(q) \implies P(q++)$. This is true because we are given that $P(m) \implies P(m++)$. The only constraint is that $q$ must be a natural number like $m$, which it is for $m \geq n$.

Let's now consider $P(q=0)$. Setting $q=0$ means $0 = m-n$, that is $n=m$. We are assuming that $P(n)$ is true. So $P(q=0)$ is true.

So we have established that for natural number $q$

• $P(q) \implies P(q++)$
• $P(q=0)$ is true

This is simply Axiom 2.5, so $P(q)$ is true for all natural numbers $q$. That is $P(q \geq 0)$ is true.

Now translating from $q$ back to $m$.

$$P(q \geq 0) \; \text{is true}$$

is the same as

$$P(m-n \geq 0) \; \text{is true}$$

That is,

$$P(m \geq n) \; \text{is true}$$

Thus we have shown $P(m \geq n)$. $\square$