Exercise 2.2.6 (Principle of backwards induction)

Hints. For the statement to prove via induction, use the following: if $P(n)$ is true, then $P(m)$ is true for all $m\le n$.

How to think about the exercise. For this kind of abstract exercise, it helps to have an example in mind. Unfortunately, I am not aware of a convincing application of backwards induction. Pete L. Clark’s notes use a very similar result (which he calls upward-downward induction) to prove the AM-GM inequality, but he also says "It is not every day that one proves a result by Upward-Downward Induction".

However, we can still play around with this a little. Suppose $P(4)$ is true. Then $P(3)$ is also true, which means that $P(2)$ is also true, which means that $P(1)$ is also true, which finally means that $P(0)$ is true. In other words, we have shown that $P(m)$ is true for all $m\le 4$, which is exactly what backwards induction claims. What if $P(5)$ is true? Then $P(4)$ is true. We already showed that if $P(4)$ is true, then $P(m)$ is true for all $m\le 4$. This means that we have now shown that $P(m)$ is true for all $m\le 5$.

I also like to translate these kinds of problems into formal logic notation, because otherwise it’s difficult to see with mathematical English where the parentheses are supposed to be. This exercise is asking us to prove the following: if $\forall <!--\; FUNCTION\; APPLICATION\; -->m(P(m++)⟹P(m))\wedge P(n)$ then $\forall <!--\; FUNCTION\; APPLICATION\; -->m(m\le n⟹P(m))$. For this kind of exercise, I encourage you to work with the formal logic notation as you’re solving the exercise, but make sure to convert back to mathematical English when writing up the exercise.

As with some induction problems, one thing you need to do is to decide on the statement you want to prove via induction. One mistake you could make is to show that $P(n)$ is true for all $n$. This is not what you want to do! In fact, given just the information in the exercise statement, it is impossible to show that $P(n)$ is true for all $n$. Another possibility is to use the statement "If $P(n)$ is true and $P(m++)$ implies $P(m)$ for all $m$, then $P(m)$ is true for all $m\le n$." This will work. However, it turns out that including the "$P(m++)$ implies $P(m)$ for all $m$" part is not necessary – you can just assume it once at the start of the exercise, so that the actual induction step will be slightly cleaner.

Model solution 1. Let $P$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, $P(m)$ is true.

Let $Q(n)$ be the following statement: if $P(n)$ is true, then $P(m)$ is true for all $m\le n$.

We shall show that $Q(n)$ is true for all $n$ using induction. For the base case, we must show $Q(0)$. So suppose that $P(0)$ is true. We want to show that $P(m)$ is true for all $m\le 0$. By definition of inequality (definition 2.2.11), $m\le 0$ means that $0=m+a$ for some natural number $a$. By corollary 2.2.9, we have $m=0$. In other words, $m\le 0$ implies $m=0$, so showing that $P(m)$ for all $m\le 0$ is equivalent to showing $P(0)$, which we already know. This completes the base case.

Now suppose $Q(n)$ is true. We must show that $Q(n++)$ is true. By definition of $Q$, $Q(n++)$ is the statement “if $P(n++)$ is true, then $P(m)$ is true for all $m\le n++$”, so suppose that $P(n++)$ is true. We need to show that $P(m)$ is true for all $m\le n++$. We know that whenever $P(m++)$ is true, $P(m)$ is true, so for $m=n$ in particular this means that if $P(n++)$ is true then $P(n)$ is true. Since $P(n++)$ is true, we see that $P(n)$ is true. By the induction hypothesis we thus have $P(m)$ for all $m\le n$. Now let $m\le n++$. We want to show that $P(m)$ is true. If we can show that $m\le n$ or $m=n++$, then we will be done, because in either case we have already shown that $P(m)$ is true. To show that $m\le n$ or $m=n++$, we will show that $m\ne n++$ implies $m\le n$. Suppose $m\ne n++$. This means $m<n++$ by definition 2.2.11. By proposition 2.2.12(e), we have $m++\le n++$, i.e. $m+1\le n+1$. By proposition 2.2.12(d) this means $m\le n$ as required. This closes the induction.

Now let $n$ be a natural number, and suppose $P(n)$ is true. By our work above, we know that $Q(n)$ is true. This means that $P(m)$ is true for all natural numbers $m\le n$ as required.

Source: Issa Rice’s blog.

Model solution 2. Let $P(m)$ be a property pertaining to the natural numbers such that whenever $P(m++)$ is true, then $P(m)$ is true. Suppose that $P(n)$ is also true. We want to show that $P(m)$ is true for all $m\le n$.

Let $Q(k)$ be the statement: for all natural numbers $m$, if $m+k=n$ then $P(m)$ is true. (The intuition here is that $Q(k)$ is basically the statement that $P(n-k)$ is true. But we can’t say $P(n-k)$ since we haven’t defined subtraction yet! So that’s why we do some first-order logic trickery to say what we want given our current tools. We know that $P(n-0)$ is true by assumption, and the rule that whenever $P(m++)$ is true, then $P(m)$ is true, means that we can go from $P(n-0)$ to $P(n-1)$, from $P(n-1)$ to $P(n-2)$, and so on, all the way to $P(n-n)$.)

We will show using induction that $Q(k)$ is true for all natural numbers $k$. For the base case, $k=0$, we want to show that for all $m$, if $m+0=n$ then $P(m)$ is true. So let $m$ be a number, and suppose $m+0=n$. Then we have $m=m+0=n$. Since we assumed $P(n)$ is true, this means $P(m)$ is true as required.

Now suppose inductively that $Q(k)$ is true. We want to show that $Q(k++)$ is true. That is, we want to show that for all $m$, if $m+(k++)=n$ then $P(m)$. So let $m$ be given, and suppose $m+(k++)=n$. Thus we have $(m++)+k=n$. By our inductive hypothesis $Q(k)$, this means that $P(m++)$ is true. We also know that whenever $P(m++)$ is true, then $P(m)$ is true. Thus $P(m)$ is true. This shows that $Q(k++)$ is true, and closes our induction.

Now suppose $m\le n$. We want to show that $P(m)$ is true. But $m\le n$ means that there exists some $k$ such that $m+k=n$. By what we showed above, we know that $Q(k)$ is true. And $Q(k)$ says that if $m+k=n$, then $P(m)$ is true, as required.

Source: Issa Rice’s blog.