Mathematical Induction: how do we know what applies to one thing also applies to another?

Question

Background:

I'm new to math. I'm learning about set theory. The book I'm reading (Schaum's Outline of Set Theory) covers mathematical induction. The book uses a common illustration and a common example (I could only find the same illustration and example when I searched on-line) to illustrate how mathematical induction works.

Illustration: "...it is like a row of standing dominoes. First, demonstrate that one standing domino falls after it is pushed. Second, demonstrate that pushing over one standing domino will knock down the second. Essentially, that proves that a row of standing dominoes will fall if the first is pushed." (taken from decodedscience.com)

Example:

"(1) 1 + 3 + 5 + ... + (2n - 1) = n^2

(2) If x_1, x_2, ..., x_n > 0 then (x_1 + x_2 + ... + x_n)/n ≥ (x1·x2·...·xn)^1/n etc.

n here is an "arbitrary" integer.

It's convenient to talk about a statement P(n). For (1), P(1) says that 1 = 12 which is incidently true. P(2) says that 1 + 3 = 22, P(3) means that 1 + 3 + 5 = 32. And so on. These particular cases are obtained by substituting specific values 1, 2, 3 for n into P(n)." (Taken from cut-the-knot.org)

What I Understand:

I know that Mathematical Induction and The Other Induction are different. I know that they are both about drawing conclusions about the general by examining the specific.

Intuitively, I can see that in the universe of math, where we have the advantage of a 'bottom-up' understanding of the laws of the universe, we can employ induction reliably

I understand that the above equations tell us that the value of a set of odd integers is equal to the square of the set's cardinal. E.g., 1+3+5 = 9. Cardinal of 3. 3^2=9.

I can see that you could apply this along the whole continuum of odd integers.

What I Don't Understand:

I don't see why those equations were used to illustrate mathematical induction. I know little about proofs, but I believe those equations are examples and not proofs. In that case, would it not have been sufficient, but trivial, to use an example like, 'an integer is always one integer greater than the integer that preceded it' n ≺ n+1

Those equations are used everywhere to illustrate mathematical induction. Nobody uses the example I just provided. So I'm assuming there is something more valuable in those equations than in my example. What is it?

I thought of some scenarios where (my understanding of) mathematical induction would be misleading. For instance, if I said that 'a prime number will be one integer greater than the prime that preceded it.' That works for the first two prime numbers (2,3), So haven't we illustrated that if you push one domino you will cause it to fall which will cause the next domino to fall...? (But in this case, the second domino will not cause the third domino to fall)

As far as I (wrongly) understand: Mathematical induction is saying that, 'you can know the infinitely applicable relationship between an input and an output, so long as you have two sets of input and output from the same continuum.'

What am I misunderstanding? Thank you for your help.

Added

• P(1) is true

• If P(*n*) is true for any n, then P(n+1)

I think that I see what I missed.

• "P(1) is true," is A
• "P(n) is true, for any n" is B
• "P(n +1) is true," is C

I thought that what you wrote meant: (A&B)->C

In words (I may have mucked up the notation): If P(1) is true; and any P(n) is true, for any n; then P(n +1). In other words: That so long as you have P(1), then for any n for which P(n) is true, you also know that the next n is true (i.e., P(n + 1)). Since the 'next n' (i.e., P(n + 1)) is true, you have another 'any n for which P(n) is true';and you can know that the n following it (i.e., P(n + 2))is also true... and you could continue this forever; thus replicating the 'domino' effect.

However, it seemed to me that it would also be possible where one could find some properties of the natural numbers for which P(1) is true, and then check that property on any other number, and by coincidence, that property may appear to be true. One would then have satisfied "P(1) is true,", and "P(n) is true, for any n"; in which case, mathematical induction would mislead one to believe that P(n) was true for all natural numbers.

I think that I should have understood that it meant: (A&(B->C))<-> 'P(n) is true for all natural numbers'.

In words:

• 'If P(1)' is true.
• And if it is also true that P(n + 1) is always true whenever 'P(n) is true, for any n'
• Only then and always then, can we say for certain that P(n) is true for all natural numbers.

I'm still curious, how "P(n + 1) is always true whenever 'P(n) is true, for any n'", without having to rely on 'evidence' (since now amount of evidence forms a proof). Is there something about mathematical induction that allows one to prove that, - or is another technique used to prove that it is true that "P(n + 1) is always true whenever 'P(n) is true, for any n'"?

Answer 1

You seem to have a general confusion regarding induction, so I'll say a couple of things in the hope that somewhere in my answer is what you're looking for.

I'll put the definition a bit formally. Let's say that we want to prove some property $P(n)$ is true for all natural numbers $n$. Mathematical induction tells us that we will have proved that if we prove that:

• $P(1)$ is true
• If $P(n)$ is true for any $n$, then $P(n+1)$

You are correct that the formulas you mention are examples, not proofs. While I don't know much about the axiomatic foundations of mathematics, as far as I know you don't really prove induction. Rather, it is taken as an axiom of the natural numbers (see Peano axioms).

The problem with your statement that any integer is always one more than the one that preceded is that it's pretty much the definition of natural numbers and induction. It's not a very useful example, because you need to know that in the first place to talk about induction.

You mention that it would be sufficient, but trivial, to use your example. That's the point: why would we mention it if it's trivial? Most explanations of induction use more elaborate examples because that way they show how induction can be used to prove useful things. There is indeed something valuable in statements like "the sum of the first $n$ odd numbers is $n^2$". Namely, they are new knowledge. If we're working rigorously with natural numbers and induction, we already know that $n+1$ is one greater than $n$, because that's the basis for everything we're doing.

Let's take a look at what's wrong with your prime numbers example. First, we need to write it a bit more formally, because to use induction we need to specify $P(n)$. We could say this: $P(n)$ is the assertion that the $(n+1)$th prime number is the $n$th prime number plus one. Let's call the $n$th prime number $p_n$. Then $p_1 = 2$, $p_2 = 3$, $p_3 = 5$, etc. $P(n)$ can now be written as $p_{n+1} - p_n = 1$.

To prove that $P(n)$ is true for all $n$, induction asks that first we prove that $P(1)$ is true. And sure enough, it's true for $n = 1$: $p_{1+1} - p_1 = 3 - 2 = 1$. So $P(1)$ is true. But the next step is where induction fails. It's not true that $P(n)$ implies $P(n+1)$. Let's say by chance we find two consecutive primes whose difference is $1$. This does not necessarily imply that it will also be true for the next pair of primes.

In terms of your analogy: we've proved that if we push the first domino it will fall, but we have not proved that if one domino falls then the next one will fall too, because in this case it's false. We can't say that if we push the first domino then all of them will fall, because we haven't proved that each domino will make the next one fall. All we know is that the first one will fall.

Regarding your definition of induction as "you can know the infinitely applicable relationship between an input and an output, so long as you have two sets of input and output from the same continuum", I must admit I don't understand it. Could you clarify what you mean with this?

Added: You seem to be confusing mathematical induction with scientific induction. In science, we can never really "prove" anything. How do we know that Einstein's relativity is true? Countless experiments and observations have been made, and every one of them agrees with relativity, so we're pretty sure it's true. But could there, in principle, be a circumstance which we haven't tested for which the law fails? Sure, and it has happened many times in the past.

Mathematical induction doesn't work this way. Say we want to prove that the sum of the first $n$ odd numbers is $n^2$. We can check for $n = 1$, and for $n = 2$, and we can check and check all day long until our calculator breaks, but we can never be sure that the statement is true for every natural number because we can't try them all. They're infinite.

Instead, (mathematical) induction provides us with a way to prove something is true for all natural numbers without individually checking all of them, something that is impossible. This is a very important point: it doesn't mean that we know something is true for a lot of numbers, so it must be true for all of them. That is false in mathematics.

When people say that there is evidence but not proof of something, that's exactly what that means. Take the Collatz conjecture, for example. Since it has been checked for a lot of numbers, most people think that it's probably right. But, and this is important again, they don't know that it's true. No one says "Well, we know the Collatz conjecture is true for $n$ up to $5000000000$, so by now we're sure it's true in general". No one says that because as long as you don't have a rigorous proof, there's always the possibility that there is an extremely high number for which the proposition fails.

Answer 2

I know that Mathematical Induction and The Other Induction are different. I know that they are both about drawing conclusions about the general by examining the specific.

It is important to see that this is absolutely wrong. Unlike empirical induction, mathematical induction is not, repeat not, about drawing conclusions about the general from specific cases. It is a way of drawing a universally generalized conclusion from a universally generalized premiss (together with an additional singular premiss). The simplest pattern for induction over natural numbers, for example, is this:

(1) For all $n$, if $P(n)$ then $P(n+1)$.

(2) $P(0)$.

Hence (3) For all $n$, $P(n)$.

Note that the crucial premiss (1) is already universally generalized. That is what enables us, with the aid of (2), to draw a universally generalized conclusion.

And the premiss (1) can't be established by looking a cases (a couple of cases or a couple of billion). It will itself have to be established by another argument from general truths (maybe by a further argument by induction, but ultimately by appeal to some basic general axioms about numbers).

Answer 3

It should also be stressed that unlike the other axioms, the principle of mathematical induction refers not just to variables, but also to properties. Thus, it would be more proper to refer to it as an axiom schema rather than an axiom - as it is a template for producing an (infinite) number of axioms, rather than being a single axiom in its own right.

Answer 4

The principle of mathematical induction (PMI) is just one of the axioms for the natural numbers. (See Peano's Axioms). In the language of set theory, it can be stated as follows:

For all subsets $P$ of $N$, if

(a) $1\in P$, and

(b) for all $x\in P$, we have $S(x)\in P$,

then $P=N$

where $S$ is the so-called successor function defined on the set of natural numbers $N$.

Peano's axioms can be described informally as follows:

1. $S$ is an injective (1-to-1) function on set $N$.
2. $1$ is an element of $N$ with no pre-image under $S$. (Guarantees the existence within $N$ of an infinite chain of succession starting at $1$)
3. The infinite chain of succession starting at $1$ includes every element of $N$. (Equivalent to PMI)