Induced Arguements ref: https://www.freemathhelp.com/forum/threads/109519-Proof-by-In

[lookagain]

This was step 1.

Moreover step 1 PROVED that there is AT LEAST one number for which the proposition is true, and there may possibly be more than one. So there is no need to assume anything in step 2.

Incorrect. Step 1 is independent from step 2. One must assume that the statement is true for n = k. And using that, one must show the statement is true for n = k + 1, which would be step 3.


[After step 1 has been shown, the following is presented.]


Assume the statement is true for n = k:

\(\displaystyle 3^{4k} \ - \ 1 \ = \ \) a multiple of 8

\(\displaystyle 3^{4k} \ - \ 1 \ = \ 8M , \ \ \ \)for some integer M.


Show the statement is true for n = k + 1:

\(\displaystyle 3^{4(k + 1)} \ - \ 1 \ = \ \) a multiple of 8

\(\displaystyle 3^{4k + 4} \ - \ 1 \ = \ \) a multiple of 8


Working with the assumption:


\(\displaystyle 3^{4k} \ - \ 1 \ = \ 8M \)

\(\displaystyle 3^4(3^{4k} \ - \ 1) \ = \ 3^4(8M) \)

\(\displaystyle 3^{4k + 4} \ - \ 81 \ = \ 81*8M \)

\(\displaystyle 3^{4k + 4} \ - \ 81 \ + \ 80 \ = \ 81*8M \ + \ 80 \)

\(\displaystyle 3^{4k + 4} \ - \ 1 \ = \ 81*8M \ + \ 80 \)

\(\displaystyle 3^{4k + 4} \ - \ 1 \ = \ 8(81M \ + \ 10) \)

\(\displaystyle 3^{4k + 4} \ - \ 1 \ = \ \) a multiple of 8


Step 4:

Thus, by the Principle of Mathematical Induction, the statement which was to be proved is true.

 

[JeffM]

Incorrect. Step 1 is independent from step 2. One must assume that the statement is true for n = k.

There is no need to assume that there is a natural number for which the proposition is true. Step 1 has already proved that there is such a number. The key difference in the so called induction step is we do not assume that such a number is necessarily 1. It is any number for which the proposition is true, and we know as a result of step 1 that it is not an empty set.

 

[stapel]

There is no need to assume that there is a natural number for which the proposition is true. Step 1 has already proved that there is such a number. The key difference in the so called induction step is we do not assume that such a number is necessarily 1. It is any number for which the proposition is true, and we know as a result of step 1 that it is not an empty set.

If we don't assume that the statement is true for n = k, then what is the purpose of proving that the statement is true for n = k + 1? We need both the proof that the statement is true at some named place (usually "n = 1") and also the proof that, if the statement is true at some (unnamed, non-specific) location, that the statement is also true at the "next" location. The assumption of the "n = k" case is what brings the two together.

For examples showing why all three parts are necessary, try here.

 

[Dr.Peterson]

I think it may help if you distinguish between "assuming that something is true" and "supposing that it is true in a particular case, so that we can talk about it". The former is either unjustified or unnecessary (depending on whether existence has been proved); the latter is what we are really doing in this step of induction.

We know that there is at least one value of n for which the proposition is true. What we need to do is to show that for any value of n for which the proposition is true, it is also true for the next value of n. So we call such a value k, and deduce that it will be true for n = k+1. That is, "suppose that k is a value of n for which the proposition is true; then we show that it is also true when n is replaced by k+1".

 

[JeffM]

If we don't assume that the statement is true for n = k, then what is the purpose of proving that the statement is true for n = k + 1? We need both the proof that the statement is true at some named place (usually "n = 1") and also the proof that, if the statement is true at some (unnamed, non-specific) location, that the statement is also true at the "next" location. The assumption of the "n = k" case is what brings the two together.

For examples showing why all three parts are necessary, try here.

\(\displaystyle x \in \mathbb X \implies x \in N^+ \text { and } P(x).\)

P(x) is the proposition that we wish to prove true. At this point, X may be the empty set.

We could go directly to \(\displaystyle k \in \mathbb X \implies k + 1 \in \mathbb X.\)

THAT is an assumption. We have no basis for assuming that any such k exists.

But that is not how we proceed. We first PROVE that \(\displaystyle 1 \in \mathbb X.\)

\(\displaystyle \therefore \mathbb X \text { is not the empty set.}\)

\(\displaystyle \text {Let } k \text { be an arbitrary member of } \mathbb X.\)

I am not assuming anything. We now PROVE \(\displaystyle k + 1 \in \mathbb X.\)

\(\displaystyle \therefore \mathbb X = \mathbb N.\)

I am not saying to do proofs by induction differently. I am not saying that proofs by induction are flawed. What I am saying is that I object pedagogically to saying ASSUME there is a k such that P(k) is true. The argument then seems circular. Assume true for k. Then prove true for k + 1. Therefore true for all numbers. Therefore true for k. That is a circular argument. Now of course that flaw does not exist in a proof by induction because we have first shown that AT LEAST one number for which the proposition to be proved is true does exist. We are then justified in saying consider any such number. There is no need to assume anything.

The traditional vocabulary causes confusion in students. It leads to imbecilic statements that steps 1 and 2 are "independent." And the traditional vocabulary is unnecessary.

 

[lookagain]

Your first two sentences in that quote box where you address stapel make no sense,
because she never stated to what you objected/emphasized. In her question, she refers
to assuming for n = k, not n = k + 1. And, in her question, it refers to proving for n = k + 1.

 

[JeffM]

Your first two sentences in that quote box where you address stapel make no sense,
because she never stated to what you objected/emphasized. In her question, she refers
to assuming for n = k, not n = k + 1. And, in her question, it refers to proving for n = k + 1.

You are correct. I have edited my post to correct that error and also to clarify my argument.

 

[stapel]

Found online:

I'm going to try and give an answer that will make sense intuitively.

Suppose you're standing on the bank of a river (for the analogy to be exactly right, it has to be an infinitely wide river, but ignore that for now), which has a number of stepping stones across it.

You know you can cross the river if you know two things: (1) you can jump to the first steppingstone, and (2) if you are standing on any of the stepping stones, you can always jump to the next one.

Part (2) is the one that feels like cheating, I know: it feels like you're using what you're trying to prove to prove itself. But in this step, you're not assuming what you're trying to prove. You're not assuming that you're standing on a stepping stone. All you're proving is that if you were, you'd be able to step to the next one.

And, if you haven't yet, please take a look at the two examples here where one or another part of the induction proof fails (as it should for false statements). My students have generally found these examples to be helpful.

 

[JeffM]

Found online:


And, if you haven't yet, please take a look at the two examples here where one or another part of the induction proof fails (as it should for false statements). My students have generally found these examples to be helpful.

The examples are cool. And they go to my point exactly. The word "assumption" has psychological connotations that do not reflect the actual logic of a proof by induction. When I work with kids, I avoid the word at all costs.

in the problem that started this discussion, the result of step 1 not only justifies that the proposition to be proved is true for at least one number k, but the fact that the proposition is true for 1 must be used to prove that the proposition is true for k + 1.

 

[Dr.Peterson]

No one has responded to my earlier suggestion: if you just use the word "suppose" instead of "assume", you lose that connotation of an arbitrary assumption, and can focus your attention on what induction is all about. To a mathematician, the two words really mean the same thing ("assume/suppose, for the sake of argument, that P(k) is true; I'll show that P(k+1) must also be true"). It's intended as a hypothetical assumption, to show that IF (the "assumed" fact is true), THEN (the conclusion will be true).

But since students initially don't see it that way, I'd want to either use "suppose" all the time, or at least emphasize what we do and do not mean by it before starting the subject.

This discussion may also be helpful, where "assume" is used, but is explained.

 

[JeffM]

No one has responded to my earlier suggestion: if you just use the word "suppose" instead of "assume", you lose that connotation of an arbitrary assumption, and can focus your attention on what induction is all about. To a mathematician, the two words really mean the same thing ("assume/suppose, for the sake of argument, that P(k) is true; I'll show that P(k+1) must also be true"). It's intended as a hypothetical assumption, to show that IF (the "assumed" fact is true), THEN (the conclusion will be true).

But since students initially don't see it that way, I'd want to either use "suppose" all the time, or at least emphasize what we do and do not mean by it before starting the subject.

This discussion may also be helpful, where "assume" is used, but is explained.

Actually, thank you for reminding me of your post. I saw it; liked it, and then got distracted. As you point out, this is about language, vocabulary, not logic.

So yes, my point is essentially about language: what is the best way to initially describe the process. And yes, you can describe it as "assume" or "suppose," but once it has been shown that the proposition is true for 1, then there is no need for either word. We now know that such numbers exist. Choose an arbitrary one of them, label it k, and prove that the proposition holds for k + 1. What I like about it is that it stresses the generality of the result and does not involve any conditional at all.

PS Yes it is a great explanation, but it was triggered by exactly the misunderstanding that the traditional vocabulary engenders.

 

[Dr.Peterson]

And yes, you can describe it as "assume" or "suppose," but once it has been shown that the proposition is true for 1, then there is no need for either word. We now know that such numbers exist. Choose an arbitrary one of them, label it k, and prove that the proposition holds for k + 1. What I like about it is that it stresses the generality of the result and does not involve any conditional at all.

I would say that this step is entirely about a conditional: IF the proposition is true for k, THEN it is true for k+1. And the way you prove such a conditional statement is to SUPPOSE that it is true for k, and conclude that it must be true for k+1. Or, ASSUME that k is a number for which it is true, and so on. The conditional statement that results is, as you say, general: whenever P(k) is true, P(k+1) is true.

Nothing here is about assuming existence; it's about assuming/supposing that a particular number is one of the numbers that have been shown to exist. In fact, as stapel's examples show, the second step can be true without the first step being true (and therefore without any existence at all); it's purely hypothetical.

So although I am in agreement with the vocabulary issue, I think you are overreacting. When properly understood (which, of course, is the real issue), "assume" or "suppose" in this context is really nothing more than "if".

 

[JeffM]

I think it may help if you distinguish between "assuming that something is true" and "supposing that it is true in a particular case, so that we can talk about it". The former is either unjustified or unnecessary (depending on whether existence has been proved); the latter is what we are really doing in this step of induction.

We know that there is at least one value of n for which the proposition is true. What we need to do is to show that for any value of n for which the proposition is true, it is also true for the next value of n. So we call such a value k, and deduce that it will be true for n = k+1. That is, "suppose that k is a value of n for which the proposition is true; then we show that it is also true when n is replaced by k+1".

I think I was far more in line with this, your original post, then how you have since developed the idea. We choose or select any of the numbers for which the proposition is true. Thus there is no need, using words in their commonly accepted senses, to say "assume" or "suppose." I agree that we may describe it as a conditional, but there is no need to do so once it has been proved that such numbers exist.

Anyway, how I choose to describe the process is not mandatory for anyone else. I have just found that students grasp the idea more easily using my vocabulary. Others may have had different experience.

 

[lookagain]

In fact, as stapel's examples show, the second step can be true without the first step being true ...

And this is how the truth value of the second step can be seen to be independent from the truth value of the first step.