In mathematical induction, why can we say if it is true for n=1, n=k and n=k+1 then it is true for all numbers?

Question

I'm having a hard time trying to grasp the concept of mathematical induction. After doing some cursory research, I believe I somewhat understand the base of it but I just stumbled upon another issue "why can we actually say if it is true for n=1, n=k and n=k+1 then it is true for all numbers?" Let's say what if it doesn't work at one specific value. For example, 3/(x-1000) is defined at x=1,2,3... but undefined at x=1000.

Sorry if this question might sound absurd to you as my mathematical knowledge is currently only at a high school level.

Also thank you so much for all of your help!

Answer 1

Suppose you want to prove $\forall x\geq 1[P(x)]$.

Suppose you have proved that $P(1)$ is true (induction base) and $\forall x\geq 1[P(x)\Rightarrow P(x+1)]$ (induction step).

Then you have proved that $\forall x\geq 1[P(x)]$. This follows from a purely logical argument (modus ponens).

In your example you cannot say (whatever the predicate $P$ is) that it holds for all $x\geq 1$. So you cannot prove it by induction.

Answer 2

This is a fantastic question. I think a good way to develop an understanding of this concept is by way of analogy...

Imagine a ladder in front of you that stretches infinitely into the sky. You would like to know whether it's possible for someone like yourself to start climbing this ladder and continue climbing it forever without stopping. So you examine the ladder and notice that although some rungs are spaced further apart than others, they are still reachable. Of course, this is only true for the rungs you are able to see; there are plenty of rungs way up the ladder too far for you to see. So now you're wondering whether there might actually be a rung that's too far to reach, somewhere way up the ladder, one that would force you too stop climbing at some point.

Hmmm... is there some way to conclude that you could reach every rung without actually being able to inspect every rung?

The answer is yes! I walk up to you and give you $1$ piece of information: "if you are able to grab any arbitrary rung on the ladder, then you will be able to grab the very next one."

You then walk up to the ladder, reach up, and grab the first rung!

That's when it hits you... I told you if you could grab ANY rung, then you could grab the very next one. So now you are certain you can grab the second rung. And then it hits you again... if you're able to grab the second rung, then must be able to grab the third. And if you're able to grab the third rung, then you must be able to grab the fourth... You quickly reason that you'll be able to grab EVERY rung on this ladder, even though you can't inspect them all. And it's all because of two little facts:

$1.$ I said if you could grab any rung on the ladder, any rung at all, then you would be able to grab the very next one.

$2.$ You observed that you could grab the very first rung.

This is precisely how mathematical induction works. The rungs on the ladder are the positive integers $\{1,2,3,...\}.$ Our goal is to conclude something about all of them, but there are infinitely many, making it impractical to inspect each one individually. Instead, we attempt to do two things:

$1.$ Show that if the statement we're proving is true for any one of them, lets call it integer $k$, then it must be true for the very next one, that is, for $k+1$.

$2.$ Show the statement we're proving is true for the very first integer in our set, that is, for the number $1$.

If you can do those two things, then you can prove your statement is true for ALL the positive integers using the same reasoning we used in the ladder analogy. This form of reasoning is called induction.

---

So now that you have an intuition for what's going on, here is a formal summary... let $P(n)$ be the statement "$n$ has such and such property." You want to prove that for every positive integer $n$, integer $n$ has such and such property, i.e. $\forall n P(n)$. You do this in two steps: a basis step and an inductive step. In the basis step, you show that integer $1$ has such and such property, i.e. $P(1)$. This is because $1$ is the least or "first" element in your set of elements you want prove something about. In the inductive step, your aim is to show that IF any arbitrary integer $k$ has such and such property, then the very next integer, $k+1$, also has such and such property, i.e. $P(k) \rightarrow P(k+1)$. This is generally done by first assuming $P(k)$ is in fact true, and then trying to derive $P(k+1)$ under that assumption. If you can, then you have successfully shown $P(k) \rightarrow P(k+1)$, and your inductive step is complete. With those two peices of information, that is, $P(1)$ and $P(k) \rightarrow P(k+1)$, you may conclude via induction that such and such is true for every integer $n$, or in other words, $\forall n P(n)$.

---

NOTE: the summary I have given is one of two forms of induction known as "weak" induction. There is also "strong" induction which makes a slightly different assumption, but both follow the same reasoning. If you can wrap your head around the ideas outlined here, then you have an intuition for how it works.