Mathematical induction method

Question

In the method of induction we take for granted the proposition P(k) and we want to prove P(k+1). Can we start from P(k+1) and prove from that that P(k) is true, or is it a wrong practise?

Answer 1

It is wrong/useless. In mathematical induction you want to move forward, not backward.

Answer 2

That is wrong. Suppose, for instance that $T(n)$ is $n\leqslant1$. Then we have $T(1)$ (since it means that $1\leqslant1$). Now, suppose that we have $T(k)$; in other words, $k\leqslant 1$. But then $k-1<k\leqslant1$ and so $k-1\leqslant 1$. So, I proved that $T(k)\implies T(k-1)$. But I hope that I don't think that$$(\forall n\in\mathbb N):n\leqslant1$$is true.

Answer 3

The principle of induction is

• prove for some $k_0$;

• prove that if true for $k$, then true for $k+1$.

Combining these two pieces, the result is guaranteed true for

$$k_0, k_0+1, k_0+2, k_0+3, \cdots$$

If you reverse the inductive argument, the result is guaranteed true for

$$k_0, k_0-1, k_0-2, k_0-3, \cdots$$

Often, the statement to prove doesn't make sense for $k<0$ or $k\le0$, and usually you want to prove for all $k\ge k_0$, not the other way.