Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
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
1  
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

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer
    
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
1  
@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$.

share|improve this answer
    
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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