Why can mathematical induction only be used with natural numbers?

Question

So, I've been learning Principle of Mathematical Induction as part of my syllabus, and so far, I've found it to be really fun to do. There's one thing I don't understand though (and none of my teachers could answer this):

Why is it necessary to use only natural numbers?

Something like real numbers or complex numbers is understandable since they can have infinite numbers between any two 'whole numbers', but what about something like integers or whole numbers? Even if taking $P(0)$ as the basic step is impossible, why not something like $P(-1)$, and then take $P(K - 1)$ as the inductive step? I don't see any reason why it isn't possible.

Answer 1

It is possible indeed, the principle of induction is much more general than you may think. There are many induction theorems you can prove for the most intuitive of them if you understand the principal idea which is well-foundedness, or well-orderedness. (but maybe it is too soon for you to benefit from the effort you would have to make to understand these notions)

---

The usual induction theorem for $\mathbb{Z}$ can be proven using regular induction. It can be stated as:

If a property $P(x)$ satisfies $P(n)$ for some integer $n$ and $\forall k \in \mathbb{Z}(P(k) \longrightarrow P(k-1) $ and $P(k+1))$, then it is true for every integer.

---

If you don't know how to prove PMI using the fact that every non-empty subset of $\mathbb{N}$ has a least element, I suggest you look for a proof. I remember I was very happy to discover this at the time I thought PMI was just some kind of common belief among mathematicians; and it is still a very interesting theorem for me.

Answer 2

I don't see any reason why it isn't possible.

It is possible--it's just simply less frequently encountered. There have been a number of posts (e.g., induction on real numbers) that deal with induction as not related to natural numbers. There have also been quite a few articles, some open source and some professionally published (not mutually exclusive), published about the matter. I recall one appearing the College Mathematics Journal not all that long ago.

Concerning your own question about something like $P(-1)$ or integers in general, there was a question a while back asked about using a negative number as a base case. The short answer is yes, you can use a negative number in your base case(s). It's just slightly atypical. For anyone not interested in seeing the answer on the other thread, below is an example of proving a claim for all $n\geq -5$ by induction.

---

Example: Suppose you have the statement $S(n)$ where $$ S(n) : n+5\geq 0, $$ and you claim this is true for all $n\geq -5$, where $n\in\mathbb{Z}$. Your base case would be $n=-5$, and this is true since $-5+5=0\geq 0$. As explained above, when we reformulate the proposition, the base case would be $T(1) = 0 = S(-5)=S(k)$. The following schematic may be easier to understand: $$ \color{blue}{T(n)}\equiv S(n+k-1) : (n+k-1)+5\geq 0\equiv n+k+4\geq 0\equiv\underbrace{\color{blue}{n-1}}_{k\,=\,-5}\color{blue}{\geq 0}\\\Downarrow\\[1em] \color{blue}{T(n): n-1\geq 0}. $$ As you can see above, proving $S(n)$ is true for all $n\geq -5$ is the exact same as proving $T(n)$ is true for all $n\geq 1$.

Answer 3

Here is an exercise in using induction, for you. Prove that, for a positive integer $n$ and a (positive) prime number $p,$ the exponent $E$ of $p$ in the prime factorization of $n!$ is Legendre's value, $$ E = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + \left\lfloor \frac{n}{p^3} \right\rfloor + \left\lfloor \frac{n}{p^4} \right\rfloor + \left\lfloor \frac{n}{p^5} \right\rfloor + \cdots $$ where eventually $p^k > n,$ so $n/p^k < 1,$ so $ \left\lfloor \frac{n}{p^k} \right\rfloor = 0.$ To emphasize, $$ p^E | n!, $$ but $p^{1+E}$ does not divide $n!$ Looking at the formula, if $p > n,$ then $E=0$ and $p$ does not divide $n!$ at all, which is what we want to happen.

There really is an induction proof. I posted it as an answer somewhere here on MSE. I could probably find it given time. EDIT: my answer at question 141196