6
$\begingroup$

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?

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

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{+\!+}.$

$\endgroup$
4
  • $\begingroup$ Great! Thanks a lot! $\endgroup$
    – dreamer
    Jul 31 '13 at 19:41
  • $\begingroup$ One question that came up, what would you say is the base case (did you include that in your answer)? $\endgroup$
    – dreamer
    Aug 1 '13 at 9:58
  • 1
    $\begingroup$ @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. $\endgroup$
    – coffeemath
    Aug 1 '13 at 11:04
  • $\begingroup$ 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? $\endgroup$ Jun 29 '19 at 3:39
6
$\begingroup$

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<n$. But from the inductive hypothesis, $P(m)$ is true $\forall$ $m\le n$ and that completes the induction. $\square$

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

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$.

$\endgroup$
4
  • $\begingroup$ 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)? $\endgroup$
    – dreamer
    Jul 31 '13 at 18:29
  • 1
    $\begingroup$ @rbm $P(n)$ was one of your assumptions in the question; you wrote "Suppose that $P(n)$ is also true." $\endgroup$ Jul 31 '13 at 18:43
  • $\begingroup$ 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? $\endgroup$ Mar 3 '17 at 6:54
  • 1
    $\begingroup$ This is a nice hack; unfortunately Tao has not introduced subtraction by the time the principle of backwards induction is presented. $\endgroup$ Jun 29 '19 at 13:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.