What is the point of induction?

Status
Not open for further replies.

The Student

Junior Member
Joined
Apr 25, 2012
Messages
241
Since k can be any positive integer, then what is the need for k+1?


Sk=1+2+3 ... +k+(k+1)

Sk+1=1+2+3 ... +k+(k+1)


They seem to be both saying the same thing?
 
Since k can be any positive integer, then what is the need for k+1?


Sk=1+2+3 ... +k+(k+1) *

Sk+1=1+2+3 ... +k+(k+1) * *


They seem to be both saying the same thing?

* This must be S(k) = 1 + 2 + 3 + ... + k


** And this must be S(k + 1) = 1 + 2 + 3 + ... + k + (k + 1)
 
Oh yes of course, but I still don't see how S(k) = 1 + 2 + 3 + ... + k implies anything different than S(k + 1) = 1 + 2 + 3 + ... + k + (k + 1). From what I think I understand about induction is that S(k+1) implies all natural numbers are possible, but doesn't S(k) also imply that?

Or, am I missing the whole point of what induction?
 
What do you mean by "all natural numbers are possible"? How does that have to do with the question you are asking? More importantly, what are you asking? Your function only collects a very small portion of the natural numbers called triangular numbers. That is S(k)=the kth triangular number.
 
Since k can be any positive integer, then what is the need for k+1?


Sk=1+2+3 ... +k+(k+1)

Sk+1=1+2+3 ... +k+(k+1)


They seem to be both saying the same thing?
Well, the way you have written them above, they are! And one statement does NOT follow from the other- indeed, they can't both be right
.
Did you mean write "Sk= 1+ 2+ 3+ ...+ k"?

In "proof by induction" you need to prove "If Sk is true (for some k) then Sk+1 is true.

If you knew that "Sk is true for all x" then it would be true for Sk+1 since that is simply a different value of k- but that is NOT what is being assumed. That is, by the way, why many people prefer to use a different symbol for the general statement than for the "induction step".

I presume you are using the example "Prove that 1+ 2+ 3+ ...+ n= n(n+1)/2"

To prove that "by induction on n", we first prove it is true when n= 1. That's typically easy- if we set n= 1, the left side is just 1 and the right side is 1(1+1)/2= 1(2)/2= 1. Yes, they are equal.

Now, we assume that, for some single value of k, 1+ 2+ 3+ ...+ k= k(k+1)/2- that is the formula above with the general "n" replace by the specific "k". We are NOT assuming this for all k or all n- that would be what we are trying to prove. We are saying "IF" that is true for a specific value of k, then
1+ 2+ 3+ ...+ k+ (k+1)= k(k+1)/2+ (k+1). That is, I have taken the sum up to k and added (k+1) to it. We can factor out (k+1) and have (k+1)[k/2+ 1]= (k+1)(k/2+ 2/2)= (k+1)(k+2)/2= (k+1)((k+1)+1)/2. That is now the same formula with n replace by k+1.

The idea is that we have prove the statement for n= 1 separately. And we have proved "if it is true for n= k= 1, it is true for n= k+1= 2". Now that we know the statement is true for n= k= 2, it must be true for n= k+1= 3. And if it is true for n= k= 3, it is true for n= k+1= 4. .... The whole point of "proof by induction" is to avoid having to say all of that!
 
Well, the way you have written them above, they are! And one statement does NOT follow from the other- indeed, they can't both be right
.
Did you mean write "Sk= 1+ 2+ 3+ ...+ k"?

In "proof by induction" you need to prove "If Sk is true (for some k) then Sk+1 is true.

I think the above sentence is a part of my misunderstanding. How can something like "Sk" or "S(k+1)" be true or false. Doesn't there have to be a presumption of some sort like 5x=20?
 
You are missing the point big time.

\(\displaystyle Let\ P_{n\ and\ m}\ be\ some\ proposition\ about\ any\ integer\ n \ge integer\ m.\)!


First, what does P n and m mean?

My professor is just showing me this for now:


If a subset S ⊂ N satisfies
(i) 1 ∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then

S = N.

To me, this just says S is a subset of N
1 is an element of S
k is an element of S only if k+1 is an element of S
then S=N. What does the k+1 have to do with anything if k can be any natural number? Instead, can't I just write:
k is an element of S, so now S=N because k can be any natural number.




 
Last edited:
Have you studied fallacies? Look up "Begging the Question".

Your task is to PROVE that all Natural Number are in S. You may not simply assume it.

Mathematical Induction does this for you.

If you can prove:

1) That 1 is in S AND
2) That k in S implies (k+1) is in S, then
3) You have proven that all natural numbers are in S.

If you simply assume that all natural numbers are in S, you are Begging the Question and you have proved nothing.
 
Have you studied fallacies? Look up "Begging the Question".

Your task is to PROVE that all Natural Number are in S. You may not simply assume it.

Mathematical Induction does this for you.

If you can prove:

1) That 1 is in S AND
2) That k in S implies (k+1) is in S, then
3) You have proven that all natural numbers are in S.

If you simply assume that all natural numbers are in S, you are Begging the Question and you have proved nothing.

But why the +1. What difference does the +1 make since k can be any natural number anyway?
 
You're not listening. You didn't look up the logical fallacy, did you?

AFTER you prove it, you can make the statements you are making. You must PROVE it first.

You do not know k = 2 is appropriate until you demonstrate it.
You do not know k = 22 is appropriate until you demonstrate it.
You do not know k = 247 is appropriate until you demonstrate it.
Stop saying "k can be anything" until AFTER you prove it so. You continue to state it before you have proven anything.

By demonstrating k = 1 is appropriate, you have demonstrated that it works for k = 1. In other words, k is in S for k = 1.
At this point, you do NOT know that k is in S for anything else. k = 1 is all you have.

By demonstrating that (k is in S) implies ((k+1) is in S), you have shown the following.

If k = 1 works, then k = 2 works.
If k = 2 works, then k = 3 works.
If k = 3 works, then k = 4 works.
If k = 4 works, then k = 5 works.
If k = 5 works, then k = 6 works.
If k = 6 works, then k = 7 works.
If k = 7 works, then k = 8 works.
etc.
If k = 74 works, then k = 75 works.
etc.
If k = 723 works, then k = 724 works.
etc.
 
You're not listening. You didn't look up the logical fallacy, did you?

AFTER you prove it, you can make the statements you are making. You must PROVE it first.

You do not know k = 2 is appropriate until you demonstrate it.
You do not know k = 22 is appropriate until you demonstrate it.
You do not know k = 247 is appropriate until you demonstrate it.
Stop saying "k can be anything" until AFTER you prove it so. You continue to state it before you have proven anything.

By demonstrating k = 1 is appropriate, you have demonstrated that it works for k = 1. In other words, k is in S for k = 1.
At this point, you do NOT know that k is in S for anything else. k = 1 is all you have.

By demonstrating that (k is in S) implies ((k+1) is in S), you have shown the following.

If k = 1 works, then k = 2 works.
If k = 2 works, then k = 3 works.
If k = 3 works, then k = 4 works.
If k = 4 works, then k = 5 works.
If k = 5 works, then k = 6 works.
If k = 6 works, then k = 7 works.
If k = 7 works, then k = 8 works.
etc.
If k = 74 works, then k = 75 works.
etc.
If k = 723 works, then k = 724 works.
etc.

I know what "begging the question" means.

I am still not sure where the k+1 is coming from. Unfortunately, my intuition says the if k+1 is an element of S then k is an element of S, and not the other way around. Just because k and 1 are elements of S wouldn't that just mean that
S={k,1}? Where is everything else coming from?

I know I am wrong and very thick with this.
 
Answering your question to my first post. If the proposition to be proved is for all positive integers, m = 1, which is the form you are asking about. If the proposition is about all non-negative integers, m = 0. If the proposition is about all integers greater than 4, then m = 5. The proposition to be proved says something about any integer n greater than or equal to m.

I am going to show you a proof by induction. After looking at the example, please reread my original post.

Mathematical induction is a method for proving propositions.

Example proposition that is to be proved: \(\displaystyle n^2 > 2n + 1\ for\ every\ integer\ n \ge 3\) In this example, m = 3.

Step 1: We prove that the proposition is true if n = m = 3.

\(\displaystyle n = 3 \longrightarrow n^2 = 3^2 = 9 > 7 = (2 * 3) + 1 = 2n + 1 \longrightarrow n^2 > 2n + 1\ if\ n = 3\)

So now the proposition has been proved for one member of the set of all integers greater than or equal to 3. An infinite number to go. But it is certainly legitimate to assume that there is at least one integer greater than or equal to 3 for which the proposition is true because we just proved that there is one, namely 3.

Step 2: We prove that for each integer for which the proposition is true the proposition is true for the next and so the next and so the next and so the next ad infinitum. At this point of course we know that it is true for one integer but we know nothing about other integers greater than m, 3 in this case.

\(\displaystyle Let\ k\ be\ an\ arbitrary\ integer\ \ge 3\ such\ that\ k^2 > 2k + 1.\) We know there is at least one.

\(\displaystyle k \ge 3 \longrightarrow k^2 \ge 3^2 = 9 \longrightarrow k^2 + 2k + 1 \ge 9 + 2k + 1 \longrightarrow\)

\(\displaystyle k^2 + 2k + 1 \ge 2k + 10 > 2k + 3 \longrightarrow k^2 + 2k + 1 > 2(k + 1) + 1.\) So it is true for the next higher.

That is: we have just proved that IF the proposition is true for k it therefore is true for k + 1, and we earlier proved that the proposition is true for 3. So it is true for 4, but then it is true for 5, and consequently it is true for 6, and so on world without end.

Edit: This may be a non-rigorous and more roundabout way to do an inductive proof and one a trained mathematican might not find acceptable. Not being a mathematician, I find this to be somewhat more intuitive than the way you presented it.

Just because it is true for k, why does that necessarily mean that it is true for k+1? If anything, I would think it should be the other way around.
 
Just because it is true for k, why does that necessarily mean that it is true for k+1? If anything, I would think it should be the other way around.
It doesn't! That's the whole point! You have to prove "If it is true for k then it is true for k+1".

That's what JeffM was doing when he wrote
\(\displaystyle Let\ k\ be\ an\ arbitrary\ integer\ \ge 3\ such\ that\ k^2 > 2k + 1.\) We know there is at least one.

\(\displaystyle k \ge 3 \longrightarrow k^2 \ge 3^2 = 9 \longrightarrow k^2 + 2k + 1 \ge 9 + 2k + 1 \longrightarrow\)

\(\displaystyle k^2 + 2k + 1 \ge 2k + 10 > 2k + 3 \longrightarrow k^2 + 2k + 1 > 2(k + 1) + 1.\) So it is true for the next higher.

That is: we have just proved that IF the proposition is true for k it therefore is true for k + 1
 
Last edited:
Just because it is true for k, why does that necessarily mean that it is true for k+1? If anything, I would think it should be the other way around.
The difficulty you are having is due to a lack of understanding of some of the basic ideas in mathematics. Mathematics is done strictly on the basis of axioms.
Axioms are neither true nor false. They are simply rules of the game.

One of the axioms for natural numbers is:
Each non-empty set of natural numbers contains a first (a smallest) term.
That is known as the well ordering axiom.
With that axiom we prove the following theorem:
If \(\displaystyle S\subset\mathbb{N} \) having these two properties: \(\displaystyle 1)~1\in S~\&~2)~k\in S\Rightarrow k+1\in S\) then \(\displaystyle S=\mathbb{N}\).

Now I said PROVE. Do you want to see it done?
 
Last edited:
The difficulty you are having is due to a lack of understanding of some of the basic ideas in mathematics. Mathematics is done strictly on the basis of axioms.
Axioms are neither true nor false. They are simply rules of the game.

One of the axioms for natural numbers is:
Each non-empty set of natural numbers contains a first (a smallest) term.
That is known as the well ordering axiom.
With that axiom we prove the following theorem:
If \(\displaystyle S\subset\mathbb{N} \) having these two properties: \(\displaystyle 1)~1\in S~\&~2)~k\in S\Rightarrow k+1\in S\) then \(\displaystyle S=\mathbb{N}\).

Now I said PROVE. Do you want to see it done?

Yes, and can you do it with the most simple example possible?
 
Yes, and can you do it with the most simple example possible?
Here are some basics. If \(\displaystyle k\in\mathbb{N}\) then \(\displaystyle k-1<k\)
Suppose that \(\displaystyle S\) has those two properties but \(\displaystyle S\ne\mathbb{N}\).
So \(\displaystyle \mathbb{N}\setminus S\ne \emptyset\). By the well ordering axiom there is a first term \(\displaystyle J\in\mathbb{N}\setminus S\). Because \(\displaystyle 1\in S\) we know the \(\displaystyle 1\ne J\)
Because
\(\displaystyle J-1<J\) then \(\displaystyle J-1\in S\).
BUT by property 2)
\(\displaystyle J-1\in S\) implies \(\displaystyle (J-1)+1=J\in S\).
Now we cannot have
\(\displaystyle J\in S\text{ and }J\notin S\) that is a contradiction.
Therefore
\(\displaystyle S\ne\mathbb{N}\) must be false so \(\displaystyle S=\mathbb{N}\) must be true.
 
I shall try one last time.

In terms of proof by induction, it is not true a priori that just because something is true of k it is true for k + 1. Example: if it is true that k is even, it is NOT true that k + 1 is even. Nor is it true that if (k + 1) is even, k is even.

You must PROVE that the proposition in question is true for (k + 1) given that it is true for k. And you must PROVE that such a k exists by proving that the proposition is true for at least one integer.

I tried to explain this informally because I am not equipped to talk about modern rigor. Formally, however, there is an axiom (due I think to Peano) that

\(\displaystyle IF\ S\ is\ a\ set\ such\ that\ (a)\ every\ member\ is\ an\ integer \ge 1, (b)\ 1 \in S, and\ (c)\ k \in S \longrightarrow (k + 1) \in S,\)

\(\displaystyle THEN\ S\ is\ the\ set\ of\ all\ natural\ numbers.\)

If I remember correctly, it is that axiom that is the foundation for proofs by induction, but notice that it is conditional. If k belongs to S entails that (k + 1) belongs to S is a condition for applying the axiom. The axiom does not say that any set containing k also contains k + 1. That must be demonstrated before the axiom applies.

Edit: Having read PKA's post, which was posted while I was writing this one, I am glad I did not claim any knowledge of modern math. I remembered what he calls a theorem as an axiom. Nor did I get Peano's axiom exactly right according to Wolfram. Peano's formulation apparently used 0 and the set of non-negative integers, but it was the same basic idea.

Furthermore, I suggest it would be better to say what you find mysterious about the example already given before asking someone to construct another example.

I think this post caused something in my head to click.
 
Here are some basics. If \(\displaystyle k\in\mathbb{N}\) then \(\displaystyle k-1<k\)
Suppose that \(\displaystyle S\) has those two properties but \(\displaystyle S\ne\mathbb{N}\).
So \(\displaystyle \mathbb{N}\setminus S\ne \emptyset\). By the well ordering axiom there is a first term \(\displaystyle J\in\mathbb{N}\setminus S\). Because \(\displaystyle 1\in S\) we know the \(\displaystyle 1\ne J\)
Because
\(\displaystyle J-1<J\) then \(\displaystyle J-1\in S\).
BUT by property 2)
\(\displaystyle J-1\in S\) implies \(\displaystyle (J-1)+1=J\in S\).
Now we cannot have
\(\displaystyle J\in S\text{ and }J\notin S\) that is a contradiction.
Therefore
\(\displaystyle S\ne\mathbb{N}\) must be false so \(\displaystyle S=\mathbb{N}\) must be true.

I think JeffM is right; I better figure out what I don't understand about this whole concept.

Getting back to this:
If a subset
S ⊂ N satisfies
(i) 1 ∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then
S = N.

Everything except the S=N part just seems to be telling me this: S = {k,1}




 
I think JeffM is right; I better figure out what I don't understand about this whole concept.

Getting back to this:
If a subset
S ⊂ N satisfies
(i) 1 ∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then
S = N.

Everything except the S=N part just seems to be telling me this: S = {k,1}



No, {k,1} does NOT contain k+1!

Because S contains k= 1, it must contain k+1= 2.
Because S contains k= 2, it must contain k+1= 3.
Because S contains k= 3, it must contain k+1= 4.
etc.
 
Status
Not open for further replies.
Top