When we can use mathematical induction and when we can't?

Question

I am in my undergraduate level, but, still it is not clear to me "When we can use induction?"

Though I have a rough idea on the later question, I think when we have a successor function which maps $P(n)\mapsto P(n+1)$, where, $P(n)$ is a proposition which depend on $n$(Correct me please if I am wrong).

Can anyone explain these in a clear way please?

Actually I think I am not able to explain the question properly, probably explaining "Why the conditions(i.e; true for $P(0)$, if true for $P(n)$ and implies $P(n+1)$ is true) are sufficient and neceassary to conclude that $P$ will hold for any $n$" will answer my question.

Answer 1

Induction is just an extended form of modus ponens, the logical rule whereby if you know that $P$ implies $Q,$ and you know that $P$ is true, then you can conclude that $Q$ is true.

The trick to induction on the integers is that when you prove that $P(n) \implies P(n+1),$ you prove many implications, one for each integer $n.$ You prove $P(0) \implies P(1),$ also $P(1) \implies P(2),$ also $P(2) \implies P(3),$ $P(3) \implies P(4),$ $P(4) \implies P(5),$ and $P(5) \implies P(6).$ And it doesn't stop there; it just keeps going and going as long as you need it to.

So let's say you have some propositional formula $P(n),$ you have proved the base case, $P(0),$ and you have proved the inductive step, $P(n) \implies P(n+1).$ Now suppose you want to show that $P(3)$ is true.

You can do this by applying modus ponens a finite number of times.

From $P(0) \implies P(1)$ and from $P(0)$ (both of which you have already proved) you can conclude that $P(1)$ is proved.

From $P(1) \implies P(2)$ and from $P(1)$ you can conclude that $P(2)$ is proved.

Finally, from $P(2) \implies P(3)$ and from $P(2)$ you can conclude that $P(3)$ is proved.

What if you wanted to prove $P(5)$? You would just need a couple more applications of modus ponens. With a few more applications, you could prove $P(17).$ To prove $P(1000000)$ this way takes a million applications of modus ponens. Few if any people would care to write out every step of such a proof, but clearly such a proof exists in principle.

What the principle of induction on the integers says is (in effect) that since you can count up to any integer by applying the successor function $n \mapsto n+1$ a finite number of times, if at each step you have the proven implication $P(n) \implies P(n+1)$ and if you have the proven base case $P(0)$ needed by the first application of modus ponens, you can (in principle) prove $P(k)$ for any integer $k$ simply by applying modus ponens $k$ times. Since $P(k)$ is provable for any integer $k$ in this way, $P(k)$ is true for every integer $k.$

So when can't you use induction over the integers? You cannot use it when a prerequisite for any single one of the applications of modus ponens for some integer $k$ is missing. If you do not have a proof for the base case $P(0),$ you do not even have the prerequisites for the first application of modus ponens, which would have proved $P(1).$ If there is even a single natural number $n$ for which your proof that $P(n)\implies P(n+1)$ is not valid, one of the applications of modus ponens is broken.

For example, there is a famous fake "proof" that all horses are the same color. (See these notes, in the middle of page 3.) In that proof, the base case is true, and it is also true that $P(n)\implies P(n+1)$ for every natural number $n$ . . . except when $n = 1.$

That one exception invalidates the entire induction. It means we cannot even prove $P(2)$ for that induction; and since we cannot do that, it is useless to know that $P(2) \implies P(3)$ or any of the other implications we could get from the inductive step for larger values of $n.$

Answer 2

Proof by induction can only be used to prove that every natural number $x$ has the some property $P$, i.e. that for all $x \in N$, we have $P(x)$ being true.

Although it may not be immediately obvious, the principle of mathematical induction is based on a fundamental property of the natural number; namely that any natural number can be reached by going from one number to the next starting at 0 (or 1 depending on which you choose to be the "first" number).

Here is how it works: Suppose you want to prove that for every $x\in N$, $x$ has property $P$, i.e. we have $P(x)$ being true. Fortunately, we do not have to test every natural number, but we do have to test the "first" number. If $0$ is your "first" number, then we would have to show that $0$ has property $P$, i.e. that $P(0)$ is true. Then we must prove that if $k \in N$ and $k$ has property $P$, then the "next" number $k+1$ must also have property $P$. To do this, assume $P(k)$ is true and then prove that P(k+1) must then also be true. And you are done! $P(0)$ is true, therefore $P(1)$ is true, therefore $P(2)$ is true, and so on.