# Induction proof strategy - backward induction

Normally, when using induction, I assume a statement is true for n, then I will try to show the same statement is also true for n+1.

In the problem I have now, is is correct if I assume a statement is true for n+1, then show that the statement is true for n, the the whole statement is true.

• You really ought to state the problem or else there's no way of knowing whether you're doing something correct. As a general principle: if you know that a proposition $P(n)$ is true for, say, $n = N$ for some large $N$, then backwards induction starting at $N$ works. Otherwise it doesn't. – Ryan Reich Nov 7 '13 at 23:09
• No. Let $P(n)$ mean $n\leq 10$. You can never get $\forall n\in \Bbb NP(n)$ – Git Gud Nov 7 '13 at 23:10

The reason why induction works is because you prove the base case.

It works as follows, let $x_n$ represent that statement "Our theorem is true for $n$".

$$x_0 \Rightarrow x_1 \Rightarrow x_2 \Rightarrow \cdots$$

and since we know $x_0$ is true we can just work up this path to conclude it is true for all $n$.

In your case you want to work backwards. To do this you need somewhere to start. For instance if you know the statement is true for $17$, and you have proved "reverse induction" you can conclude it is true for all $n\le 17$ as follows:

$$x_{17} \Rightarrow x_{16} \Rightarrow x_{15} \Rightarrow \cdots \Rightarrow x_{0}$$

But you see you have to have somewhere to start to work your way down this trail. So this method will never imply something is true for all natural numbers.

• Unless you use induction to show $\forall n\in\mathbb{N}(n\leq k\to P(n))$ for all $k\in\mathbb{N}$! Oh... – Malice Vidrine Nov 7 '13 at 23:24
• @MaliceVidrine That doesn't contradict Deven's statement that it can't be proven that $\forall n\in \Bbb NP(n)$. – Git Gud Nov 7 '13 at 23:27
• Yeah, sorry, I was being silly. – Malice Vidrine Nov 7 '13 at 23:31
• In my problem, a statement is given at later point n= N, and I have to show that statement is true at n= 0. – Peter Nov 7 '13 at 23:32
• @Peter That is what the answer addresses. You can show by backward induction that the statement is true for $n$ if and only if $n<N$. Given of course that backward induction can be used in the first place. – Jaycob Coleman Nov 7 '13 at 23:35