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.

Please give the insight.

  • 1
    $\begingroup$ 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. $\endgroup$ – Ryan Reich Nov 7 '13 at 23:09
  • 1
    $\begingroup$ No. Let $P(n)$ mean $n\leq 10$. You can never get $\forall n\in \Bbb NP(n)$ $\endgroup$ – 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.

  • $\begingroup$ Unless you use induction to show $\forall n\in\mathbb{N}(n\leq k\to P(n))$ for all $k\in\mathbb{N}$! Oh... $\endgroup$ – Malice Vidrine Nov 7 '13 at 23:24
  • $\begingroup$ @MaliceVidrine That doesn't contradict Deven's statement that it can't be proven that $\forall n\in \Bbb NP(n)$. $\endgroup$ – Git Gud Nov 7 '13 at 23:27
  • $\begingroup$ Yeah, sorry, I was being silly. $\endgroup$ – Malice Vidrine Nov 7 '13 at 23:31
  • $\begingroup$ In my problem, a statement is given at later point n= N, and I have to show that statement is true at n= 0. $\endgroup$ – Peter Nov 7 '13 at 23:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Jaycob Coleman Nov 7 '13 at 23:35

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.