# Proof of the principle of backwards induction

I have difficulty in neatly writing down a proof for the following from Terence Tao's Analysis I, where $$m{+\!+}$$ is the successor function:

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$. Jul 31 '13 at 17:46
• What does $a++=n$ mean? Jul 31 '13 at 17:52
• 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. Jul 31 '13 at 18:04
• But a++ in programming means b=a; a=a+1; return b; which is why this usage is a mess. 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. Jul 31 '13 at 18:29

## 4 Answers

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! 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)? 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. Aug 1 '13 at 11:04
• Seriously awesome. I have never seen induction on the thorem itself before and feel like a Philistine. To make sure I grok your proof: You are given that α is true and you are asked to prove β. You proved that 'α=>β' is true. Thay doesn't imply β is true. You need to say that 'α and α=>β imply β is true'. Nitpicking just to confirm that I really understand your proof. Do I have this right? Jun 29 '19 at 3:39

Proof: Let $$n \in \mathbb{N}$$. Using induction on $$n$$, for the base case $$n = 0$$, we need to show that $$P(m)$$ is true $$\forall\ m\le 0$$. But only $$0\le 0$$ so we just need to show that $$P(0)$$ is true. Since $$P(n)$$ is true from the hypothesis, $$P(0)$$ is true and that completes the base case.

Suppose inductively that the principle if true for $$n$$, i.e $$P$$ is such that $$P(n)$$ is true, and whenever $$P(m{+\!+})$$ is true, $$P(m)$$ is true $$\forall m\le n$$. We have to show the principle is true for $$n{+\!+}$$ i.e we need to show that $$P(m)$$ is true $$\forall\ m\le n{+\!+}$$ given that $$P(n{+\!+})$$ is true and given that whenever $$P(m{+\!+})$$ is true, $$P(m)$$ is true.

Since $$P(n{+\!+})$$ is true, then $$P(n)$$ is also true. So we have to show that $$P(m)$$ is true $$m. But from the inductive hypothesis, $$P(m)$$ is true $$\forall$$ $$m\le n$$ and that completes the induction. $$\square$$

• This is the same as the answer by coffemath and posted two years earlier. How come this is not the accepted answer? Jun 29 '19 at 13:31
• @MarcusJuniusBrutus Read dates carefully. Jun 18 at 20:38

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)? 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." Jul 31 '13 at 18:43
• It seems that assuming well-ordering of the naturals, it's quite easy for students to prove variants of standard induction (complete, backward, forward-backward...). But to show that these variants hold using standard induction requires students to modify the proposition to be proved (in your case, it's $n-k \geq 0 \implies P(n-k)$), which students find difficult. Any tips and ideas that students can practise and use to improve this skill? Mar 3 '17 at 6:54
• This is a nice hack; unfortunately Tao has not introduced subtraction by the time the principle of backwards induction is presented. Jun 29 '19 at 13:28

Same answer as @coffeemath but made more clear. The statement to be proved is this:

$$\forall n\in \textbf{N}, \Bigg (P(n) \implies (\forall m \le n, P(m)) \Bigg )$$

which we can rewrite as, taking $$R(n) := (\forall m \le n, P(m))$$

$$\forall n\in \textbf{N}, \Bigg (P(n) \implies R(n) \Bigg )$$

Define $$Q(n):=(P(n) \implies R(n) )$$. We want to show $$\forall n\in \textbf{N}, Q(n)$$ and we shall use the principle of mathematical induction on $$Q(n)$$.

Step 1: $$Q(0):=(P(0) \implies R(0) )\equiv (P(0) \implies P(0) )$$. Thus, Q(0) is true.

Step 2: Assume $$Q(n)$$ is true.

Step 3: Since $$P(n{+\!+})\implies P(n)$$ and $$P(n) \implies R(n)$$, we have $$P(n{+\!+}) \implies R(n)$$. (syllogism). Now $$(P(n{+\!+}) \implies R(n)) \equiv (P(n{+\!+}) \implies R(n)) \land P(n{+\!+})) \equiv (P(n{+\!+}) \implies R(n{+\!+})) \equiv Q(n{+\!+})$$.

Hence $$Q(n)$$ is true $$\forall n$$. QED.