# Proof of the principle of backwards induction

I have difficulty in neatly writing down a proof for the following:

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, then $P(m)$ is true. Suppose that $P(n)$ is also true. Prove that $P(m)$ is true for all natural numbers $m\leq n$; this is know as the principle of backwards induction. (Hint: apply induction to the variable $n$.)

First of all, I am unsure about what the base case should look like. For the induction step, I understand that if we suppose inductively that $P(n)$ is true, that then for a natural number $a$ s.t. $a++=n$ it holds that $P(a)$ is true, and then for a natural number $b$ s.t. $b++=a$ it holds that $P(b)$ is true etc. Hence for all natural numbers $m\leq n$, $P(m)$ is true.

Could anyone please tell me what the base case should look like, and whether there is a neater way of writing down the induction step?

-
Seems to me that the hint is a little misleading. The way I would approach this is try to prove that for any $a \leq n$, $P(m)$ is true for all natural numbers $n - a \leq m \leq n$, by induction on $a$. – Scaramouche Jul 31 '13 at 17:46
What does $a++=n$ mean? – Asaf Karagila Jul 31 '13 at 17:52
This question was asked the other day (or at least a very similar question), see here. – Kenny Hegeland Jul 31 '13 at 18:00
I also believe that rbm is reading from Tao's analysis where he uses $++$ to represent the successor when constructing $\Bbb{N}$ from the Peano axioms. – Kenny Hegeland Jul 31 '13 at 18:04
Using $++$ is by all means a horrible mathematical notation. In particular since $+$ itself is already in the language and is a binary operator. Using $s$ or $S$ is much clearer and common enough, at least in logic. – Asaf Karagila Jul 31 '13 at 18:29

This answer is to show the statement can be proved on (upward) induction on $n$, as in the hint.

Suppose the statement holds at a specific $n$. The statement of it for $n++$ is then:

Suppose $P(n++)$ is true, then it follows that $P(m)$ holds for all $m \le n++.$

From the assumption that $P(n++) \implies P(n),$ we arrive at $P(n)$ true, so that from the inductive hypothesis $P(k)$ holds for all $k \le n$. Together with the assumption that $P(n++)$ holds, we have the desired conclusion of the inductive step, i.e. that $P(m)$ holds for all $m \le n++.$

-
Great! Thanks a lot! – dreamer Jul 31 '13 at 19:41
One question that came up, what would you say is the base case (did you include that in your answer)? – dreamer Aug 1 '13 at 9:58
@rbm No I didn't since it seems too obvious. It would just say (for $n=1$): Suppose $P(1)$ holds. Then $P(m)$ holds for all $m \le 1$. But there's only one such $m$, namely $1$, so that there is nothing to show for the base case. – coffeemath Aug 1 '13 at 11:04

Prove, by ordinary induction on $k$, the statement "if $n-k\geq0$ then $P(n-k)$. The base case is $P(n)$, and the induction step, going from $k$ to $k+1$, comes from the "backward induction" hypothesis, because increasing $k$ decreases $n-k$.

-
Thank you for your help! That is a nice way of converting it to an ordinary induction problem. One question that I have; how exactly does the base case work (why would $P(n)$ hold true)? – dreamer Jul 31 '13 at 18:29
@rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true." – Andreas Blass Jul 31 '13 at 18:43