What's the point of inductive proofs?

[TysonM8]

Ok, I'm really confused with the reasoning behind inductive proofs.

To prove some statement is true for all natural numbers, you need to assume the statement is true for some number k. But aren't you really assuming the statement is true for all natural numbers in the first place? If you can find some number k for which the statement isn't true, it is not true for k+1. So the statement HAS to be true for k, for it to be true for k+1. So aren't you just assuming a statement is true to prove it is true? Sounds like a circular argument to me.

Note: I've only just started learning inductive proofs so sorry if I've misunderstood something :)

 

[pwsnafu]

A few things. All math is "if A then B". With induction it's A = "proposition is true for k" and B = "proposition is true for k+1" Be aware there is a difference between assuming something is true and proving something is true.

That alone is not enough. What makes it work is the base case. Let's pick k=2. We prove the statement directly for k=2.
Then we know it is true for k=2 (this is "A") therefore it is now true for k=3 (this is "B").
Then we know it is true for k=3 (this is "A") therefore it is now true for k=4 (this is "B").
And so on. It's dominoes falling. The base case is the initial push, and the induction step is the dominoes hitting the next one.

 

[mfb]

Oh ok, I understand. But I still don't see the point of it if you can find cases where induction fails

Induction does not fail.

If you can do a "proof" by induction and then prove it wrong by contradiction

You cannot, unless you made an error somewhere.

 

[HallsofIvy]

By the way, I would never use the phrase "inductive proof". It is too easy to confuse that with "inductive reasoning" which quite a different thing. Use instead "proof by induction".

To prove some statement is true for all natural numbers, you need to assume the statement is true for some number k. But aren't you really assuming the statement is true for all natural numbers in the first place?

No, you are not. "Proof by induction" requires two things:
(1) prove the statement is true for n= 1 (or, more generally, n= 0 or some other starting value).
(2) prove that "if the statement is true for k then it is true for k+ 1".
"k" is always a single positive integer, not "all natural numbers".

One could now reason "I have proved the statement true for k= 1 so, by (2), it is true for k+ 1= 1+ 1= 2. I have now proved it is true for k= 2 so, by (2), it is true for k+ 1= 2+ 1= 3. I have now proved it is true for k= 3 so, by (2), it is true for k+1= 3+ 1= 4. ..." "Proof by induction" is just a short way of stating that obvious infinite sequence.

 

[D H]

Ok, I'm really confused with the reasoning behind inductive proofs.

To prove some statement is true for all natural numbers, you need to assume the statement is true for some number k. But aren't you really assuming the statement is true for all natural numbers in the first place? If you can find some number k for which the statement isn't true, it is not true for k+1. So the statement HAS to be true for k, for it to be true for k+1. So aren't you just assuming a statement is true to prove it is true? Sounds like a circular argument to me.

Note: I've only just started learning inductive proofs so sorry if I've misunderstood something :)

What you are missing is the base case. To prove something by induction you need to prove

1. That if the hypothesis is true for some number k then it is true for k+1.
2. That the hypothesis is true for k=1.

The first item that one needs to prove is called the inductive step. The second item is called the base case. Both are needed for induction. The inductive step doesn't stand by itself; what if the hypothesis isn't true for k? The base case and the inductive step together are what prove the hypothesis true for all k.

Suppose you have proved the inductive step and the base case for some hypothesis. Start with k=1. We know that the hypothesis is true here because you proved it. The inductive step says that the hypothesis is true for k=2. Applying the inductive step to the case k=2 means the hypothesis is also true for k=3. And so on. Once you have the inductive step and the base case proven, the hypothesis is necessarily true for all natural numbers.

 

[Axiomer]

I like thinking of induction by thinking of an infinite sequence of dominoes. The base case proves that the first domino falls over. The inductive step proves that if some domino falls over, then the next domino will necessarily fall over. Knowing that these two claims are true, we are reasonably convinced that every domino in the sequence will eventually fall over.

An important thing to note is that you can prove that induction works if you assume the well-ordering principle, the statement that every subset of the natural numbers has a least element. So if you aren't convinced that induction works, it may be easier to convince yourself that every subset of the natural numbers has a least element!

 

[economicsnerd]

Another way of viewing induction. Say I have some proposition P(k) associated with each positive integer k\in\mathbb N.

Suppose somebody else has proven, for each k\in \mathbb N, the following Lemma, which I'll call Lemma(k):
\textbf{If } P(n) \text{ is true for every } n\in\mathbb N \text{ with } n<k, \textbf{ then } P(k)\text{ is true as well.}
Now I can use these lemmas to prove the following Theorem: P(k) \text{ is true for every } k\in\mathbb N.
My proof:
-Consider any k\in \mathbb N. Rephrasing Lemma(k), it can't be the case that k is the smallest natural number for which P fails.
-So there can be no first k such that the proposition fails. But if it sometimes failed, it would (because of the well-ordering property of \mathbb N) have to have a first failure. Thus P can never fail. i.e. P(k) is true for every k\in\mathbb N.
This concludes the proof.

~~~~~~~~

When somebody does a proof by induction, they really have this argument going on in the background. Given that, it's common practice to just prove Lemma(k) for every k and not make the rest of the argument explicit.

So where does this "base case" / "inductive step" distinction come in? It just turns out that quite often:
a) The proof of Lemma(k) looks very similar for every k\geq 2. In this case, they can all be proven simultaneously, and they're collectively called the inductive step.
b) Lemma(1) can be equivalently stated as "P(1) is true". Sometimes it's obvious, and sometimes it requires a qualitatively different proof from the other lemmas. So people sometimes separate it out and call it the base case.

 

[baker0]

Another way of viewing induction. Say I have some proposition P(k) associated with each positive integer k\in\mathbb N.

Suppose somebody else has proven, for each k\in \mathbb N, the following Lemma, which I'll call Lemma(k):
\textbf{If } P(n) \text{ is true for every } n\in\mathbb N \text{ with } n<k, \textbf{ then } P(k)\text{ is true as well.}
Now I can use these lemmas to prove the following Theorem: P(k) \text{ is true for every } k\in\mathbb N.
My proof:
-Consider any k\in \mathbb N. Rephrasing Lemma(k), it can't be the case that k is the smallest natural number for which P fails.
-So there can be no first k such that the proposition fails. But if it sometimes failed, it would (because of the well-ordering property of \mathbb N) have to have a first failure. Thus P can never fail. i.e. P(k) is true for every k\in\mathbb N.
This concludes the proof.

~~~~~~~~

When somebody does a proof by induction, they really have this argument going on in the background. Given that, it's common practice to just prove Lemma(k) for every k and not make the rest of the argument explicit.

So where does this "base case" / "inductive step" distinction come in? It just turns out that quite often:
a) The proof of Lemma(k) looks very similar for every k\geq 2. In this case, they can all be proven simultaneously, and they're collectively called the inductive step.
b) Lemma(1) can be equivalently stated as "P(1) is true". Sometimes it's obvious, and sometimes it requires a qualitatively different proof from the other lemmas. So people sometimes separate it out and call it the base case.

This is the real argument here. As economicsnerd pointed out, for a family of statements f(n), where n varies over a nonempty collection of the positive integers, if one of these statements is false, then there is a first false statement. Why is this the case? This follows from the fact that a nonempty collection of positive integers has a smallest number in it. You can use this in turn to proof that mathematical induction works. All you do is prove that if
- f(1) is true
and
- if f(n) is true f(n+1) is true
then the collection of positive integers such that f(n) is false is the empty set. Try to assume that this collection is nonempty and you should be able to reach a contradiction.