## Mathematical Induction - Introductory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Flumble wrote:
MathDoofus wrote:
Meteoric wrote:But you don't seem to know how to prove them, which is what we're doing here. We keep circling around this same problem. The induction step is just a conditional proof.

If I demonstrate that a base case is true, and then demonstrate that if the k case is true then the (k + 1) case is true, then I've shown that the whole ball of wax is true.

Indeed, so that's why you can show with induction that every positive number is odd or even:
neveroddoreven-2-electric-boogaloo.png
(click it for a readable size)

Induction may well be the weirdest way to prove that every positive number is odd or even (you'd rather directly prove for every number that, for example, when dividing by two, you end up with a remainder of 0 or 1, meaning it's even or odd), but it's one of the most accessible statements that can be proven with induction.

It is too much of a mental stretch (for now) for me to relate the even-odd "proof" to a statement about P(n), a base case, a k case, and a (k + 1) case, much less the conditional framework. It just doesn't line up with that method of analysis for me.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:INDUCTION STEP: Assume that k is either even or odd. If k is even, then k+1 is odd. If k is odd, then k+1 is even. So either way, k+1 is either even or odd.

I assumed k is either even or odd, then used it to prove that k+1 is. That's how you say I should prove "If k is either even or odd, then k+1 is either even or odd".

I have answered your exact question about step 2 before. So no, I think I literally can't help you with it, not until we get some more fundamental questions nailed down.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:
Meteoric wrote:INDUCTION STEP: Assume that k is either even or odd. If k is even, then k+1 is odd. If k is odd, then k+1 is even. So either way, k+1 is either even or odd.

I assumed k is either even or odd, then used it to prove that k+1 is. That's how you say I should prove "If n is either even or odd, then k+1 is either even or odd".

I have answered your exact question about step 2 before. So no, I think I literally can't help you with it, not until we get some more fundamental questions nailed down.

If you want to continue down the even-or-odd induction proof path, then please (for my sanity) explain, using the contents and steps of that even-or-odd proof, how each piece of content and each step from that proof relates to if/then statements and the steps of the original induction proof that I've been working on. I need a piece-by-piece explanation, please.

And I still need help moving on from Step 2 in the original proof by induction. No one seems to be able to tell me what the next step is and how that next step relates (if at all) to the substitution of (k + 1) for all instances of k.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

I will be happy to give such a step-by-step when I am back at a real keyboard, but that will have to wait a few hours.

The reason I am avoiding your question about step 2 is that, last time, we spent a full page on the same question, concluding with you saying "I give up". We explained and gave you the answer outright, but you seemed even more confused by it. That's when I started backing up to looking at the components by themselves, so that we can put them together later.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:I will be happy to give such a step-by-step when I am back at a real keyboard, but that will have to wait a few hours.

The reason I am avoiding your question about step 2 is that, last time, we spent a full page on the same question, concluding with you saying "I give up". We explained and gave you the answer outright, but you seemed even more confused by it. That's when I started backing up to looking at the components by themselves, so that we can put them together later.

Thank you - I'm fine with waiting (and thank you for your patience with me as well). The last time around, no one directly answered my question about the substitution step, why it may or may not be necessary, and how it relates to Step 2. Instead, the answers were more questions about "what are we trying to prove, etc." which of course may be good pedagogical techniques but don't answer my very straightforward questions.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

There is no substitution step. We add stuff to both sides, rearrange, and that's it.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:There is no substitution step. We add stuff to both sides, rearrange, and that's it.

No, I'm certain that there's a substitution step - others have referenced it in this thread.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

There is not.

You can write the proof a different way, in which you use substitution INSTEAD of adding to both sides. But since you're talking about step 2, where you have already added to both sides, you are definitely not using that way.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:There is not.

You can write the proof a different way, in which you use substitution INSTEAD of adding to both sides. But since you're talking about step 2, where you have already added to both sides, you are definitely not using that way.

OK. Then what do I need to do to get from Step 2 to Step 3?

Flumble
Yes Man
Posts: 2137
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:If you want to continue down the even-or-odd induction proof path, then please (for my sanity) explain, using the contents and steps of that even-or-odd proof, how each piece of content and each step from that proof relates to if/then statements and the steps of the original induction proof that I've been working on. I need a piece-by-piece explanation, please.

Let me explain with another picture:

(the part in red is all the algebra steps that transform the (assumed) truth for k to the truth for k+1; please assume it is correct like the logical steps in the odd-or-even problem for the purpose of learning induction. Alternatively, please assume the induction proof is sound for the purpose of learning the algebra within the red section —as has been said before, these are seperate branches of math to learn ...though you need to learn both to fully understand the proof of this triangular number equality.)

Compare it to the previous picture.
As you can see, the structure is the same: the induction axiom (the long sentence) is still there, there's still a statement for it, there's a branch proving the base case, there's a branch proving the induction step and there's a conclusion rolling out of it. However the statement has changed (quite obviously) and therefore the contents of the base case, the induction step and the conclusion are different.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Flumble wrote:
MathDoofus wrote:If you want to continue down the even-or-odd induction proof path, then please (for my sanity) explain, using the contents and steps of that even-or-odd proof, how each piece of content and each step from that proof relates to if/then statements and the steps of the original induction proof that I've been working on. I need a piece-by-piece explanation, please.

Let me explain with another picture:
induction-proof-for-triangle-problem.png
(the part in red is all the algebra steps that transform the (assumed) truth for k to the truth for k+1; please assume it is correct like the logical steps in the odd-or-even problem for the purpose of learning induction. Alternatively, please assume the induction proof is sound for the purpose of learning the algebra within the red section —as has been said before, these are seperate branches of math to learn ...though you need to learn both to fully understand the proof of this triangular number equality.)

Compare it to the previous picture.
As you can see, the structure is the same: the induction axiom (the long sentence) is still there, there's still a statement for it, there's a branch proving the base case, there's a branch proving the induction step and there's a conclusion rolling out of it. However the statement has changed (quite obviously) and therefore the contents of the base case, the induction step and the conclusion are different.

Thank you! Unfortunately, the algebra steps are (mostly) too small to be legible, although I think I did spot a substitute (k + 1) step, which everyone here told me isn't a step in working the problem.

Flumble
Yes Man
Posts: 2137
Joined: Sun Aug 05, 2012 9:35 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:Unfortunately, the algebra steps are (mostly) too small to be legible

Do you mean conceptually? Because you can click the image for a full resolution version that you can read ...and you can click the full resolution image again to zoom it to actual scale, assuming you don't have an expensive ultra-high resolution monitor.

MathDoofus wrote:a substitute (k + 1) step, which everyone here told me isn't a step in working the problem.

That's a miscommunication –I haven't followed the discussion closely enough to understand what exactly is misunderstood and by whom, but there's definitely a miscommunication in there.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Flumble wrote:
MathDoofus wrote:Unfortunately, the algebra steps are (mostly) too small to be legible

Do you mean conceptually? Because you can click the image for a full resolution version that you can read ...and you can click the full resolution image again to zoom it to actual scale, assuming you don't have an expensive ultra-high resolution monitor.

MathDoofus wrote:a substitute (k + 1) step, which everyone here told me isn't a step in working the problem.

That's a miscommunication –I haven't followed the discussion closely enough to understand what exactly is misunderstood and by whom, but there's definitely a miscommunication in there.

I was told by others that, in the way that I've worked the problem, there's no step where (k + 1) is wholesale substituted for all instances of k. No one has said why that's so. Nor has anyone told me how to proceed from Step 2, which is where I've been stuck for most of the day.

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5493
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

### Re: Mathematical Induction - Introductory Question

After having proved that the formula is valid for all n, you can replace n with k+1. If you do that, you get
sum to k+1 = (k+1)(k+2)/2

What you have to do for the proof is show that, IF the formula is true for n=k, THEN the formula for n=k+1 works
So ok, you write down the formula for n=k
sum to k = k(k+1)/2

alright, now you add k+1 to both sides
sum to k+1 = k(k+1)/2 + k+1

So now you have a proposal
k(k+1)/2 + k+1 ?= (k+1)(k+2)/2
Where the ?= is a "maybe it's equal" sort of thing

And then you do the arithmetic
Get some least common denominator going on
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

doogly wrote:After having proved that the formula is valid for all n, you can replace n with k+1. If you do that, you get
sum to k+1 = (k+1)(k+2)/2

At which step do I "prove[ ] that the formula is valid for all n"? I'm confused by that statement.

Please - can someone tell me directly what comes after Step 2 in my (many) earlier posts, and why?

WibblyWobbly
Can't Get No
Posts: 506
Joined: Fri Apr 05, 2013 1:03 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:
MathDoofus wrote:
WibblyWobbly wrote:It's because your original goal, in all of this induction, is to prove that there is a nice, simple formula for finding the sum of the first n positive integers. That formula is n(n+1)/2. You're trying to prove this is true for all positive integers, right?

k is just a positive integer.
k+1 is just a (different) positive integer.

We get the k-case by substituting k for n in n(n+1)/2, right? So why can't we get the (k+1)-case from substituting (k+1) for n in n(n+1)/2, too? The answer is that we can.

Still at Step 2 and trying figure out which steps come next, and why:

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

Can you help with that?

Can anyone help me with this? Thank you.

Sorry. Wasn't feeling well earlier.

So here's what comes next:

Show that k(k+1)/2 + (k+1) = (k+1)((k+1)+1)/2

Here's why:

Remember, the original equation, which was the thing to be proven, was:
"Sum of the first n positive integers" = 1 + 2 + 3 + ... + n = n(n+1)/2

You started with the k-case, which comes from substituting k for n in the original equation:
1 + 2 + 3 + ... + k = k(k+1)/2

You turned this into (connected it with) the (k+1)-case by adding (k+1) to both sides:
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)

So this is the (k+1)-case. But as we discussed earlier, you can also get the (k+1)-case in a similar manner to how you originally got the k-case: by substituting (k+1) for n in the original equation:

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

This is also the (k+1) case. So we have two equations that are both the (k+1)-case? We can get it from two totally different approaches?
The answer is no, not really. The reason is that the two forms we have for the (k+1)-case are actually absolutely the same. Your job (the next step) is to prove it. Directly.

So your job is to take the equation that you're at right now:
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)

and show that it is the same as
1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2

Now, the left-hand sides of those equations are already identical, right? So the way we prove that those two equations are equivalent is to show that the right-hand sides are equal, that is:
k(k+1)/2 + (k+1) = (k+1)((k+1)+1)/2

Try expanding out both sides. You'll end up with k2 terms on both sides - that's fine. Just try to carry out the expansions and see where you get.

WibblyWobbly
Can't Get No
Posts: 506
Joined: Fri Apr 05, 2013 1:03 pm UTC

### Re: Mathematical Induction - Introductory Question

Flumble wrote:
MathDoofus wrote:a substitute (k + 1) step, which everyone here told me isn't a step in working the problem.

That's a miscommunication –I haven't followed the discussion closely enough to understand what exactly is misunderstood and by whom, but there's definitely a miscommunication in there.

This is absolutely correct - there was a miscommunication somewhere, but there is no step where (k+1) is substituted for k.

You start with the original equation:
1 + 2 + 3 + ... + n = n(n+1)/2

You use this to get the k-case, by substituting k for n (this is the first part of the induction step: assume the original equation is true for some n = k):
1 + 2 + 3 + ... + k = k(k+1)

You also use this to get one form of the (k+1)-case by substituting (k+1) for n (this is in the second part of the induction step, where we seek to prove that if the original equation is true for some n = k, it is also true for some n = (k+1)):
1 + 2 + 3 + ... + k + (k+1) = (k+1)((k+1)+1)/2

The only two examples of substitution are these, where we substitute something for n in the original equation. There is no step in this procedure where you substitute (k+1) for k. So just put that notion out of your mind - it was a miscommunication on our part somewhere along the line.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:If you want to continue down the even-or-odd induction proof path, then please (for my sanity) explain, using the contents and steps of that even-or-odd proof, how each piece of content and each step from that proof relates to if/then statements and the steps of the original induction proof that I've been working on. I need a piece-by-piece explanation, please.

Okay, let me now attempt to provide such an explanation.

In both problems, we seem to be clear on the base step.

Then we move to the induction step:
1. Assume that k is either even or odd. [ASSUMPTION] "the k case"
2. If k is even, then k+1 is odd. [TRUE BECAUSE: adding 1 flips parity]
3. On the other hand, if k is odd, then k+1 is even. [TRUE BECAUSE: adding 1 flips parity]
4. So either way, k+1 comes out either even or odd. [TRUE BECAUSE: combines steps 2 and 3] "the k+1 case"
The k case and the k+1 cases are statements. Everything in between is also a statement, justified by known rules of mathematics. The nice thing about this problem is that all of our statements are ordinary English sentences, and everything is totally obviously true. Why did we take the steps we did? Well, because they get us from the k case to the k+1 case.

Now, in our original problem, the k case and the k+1 cases are still statements. Namely, they are equations. If you read an equation out loud, it forms a complete English sentence - specifically a statement, as opposed to a question or command or etc. Unfortunately, these statements are more unwieldy than above:

1. Assume that 1+...+k=k(k+1)/2. [ASSUMPTION] "the k case"
2. Then 1+...+(k+1)=k(k+1)/2 + (k+1) [TRUE BECAUSE: add (k+1) to both sides of step 1]
3. Simplifying the expression on the right side, k(k+1)/2+(k+1)=(k+1)(k+2)/2 [TRUE BECAUSE: do some algebra to combine terms]
4. Then 1+...+(k+1)=(k+1)(k+2)/2 [TRUE BECAUSE: combines steps 2 and 3] "the k+1 case"

Again, we started with a statement of the k case, made some other statements justified by the rules of mathematics, and deduced the statement of the k+1 case. But this time, our statements were fancier and our justifications involved a lot more algebra. Why did we take the steps we did? Well, because they get us from the k case to the k+1 case.

It seems that you have questions about the even/odd proof, but the questions you're asking map exactly onto things you're struggling with in the original problem. And in the even/odd proof, we can examine those questions with much smaller statements that can be easily stated in English, without getting bogged down in a ton of algebra.
No, even in theory, you cannot build a rocket more massive than the visible universe.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:It seems that you have questions about the even/odd proof, but the questions you're asking map exactly onto things you're struggling with in the original problem.

Let me give some explicit examples of this.

Here, you are asking why the even/odd proof is valid, even though we haven't established specifically which of the two k+1 is:
MathDoofus wrote:
Meteoric wrote:
I agree that it is a very trivial induction proof. It does not address any of the problems you're having with algebra in the original problem. That is why I am also recommending that you practice algebra, separately, as an independent skill. Once you do that, you will find that the algebra is also very simple. Then all you'll have is simple algebra, and a simple proof structure, and so the whole thing will be easy.

Right now, you're having trouble because you don't understand the individual parts of the proof.

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

And here, you were having trouble with the original proof:
MathDoofus wrote:
Meteoric wrote:
Yes, at the fourth step, I have the following:

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

Not sure what you're asking about with respect to the "equation [I'm] trying to prove."

Back up and think about it for a few minutes - I could tell you directly, but I don't think that would help as much. It's very important that you know what is being proven.

At the induction step, your goal is to prove that "k case ⇒ k+1 case". In this specific problem, what is the k+1 case?

The (k + 1) case would be replacing all references to k with (k + 1), yes? But I'm not sure whether I do that on both the left and right sides of the equation above!

In both of these situations, you are having trouble because you are conflating the k+1 case with the steps that will be used to prove it, and because you can't identify which statement is "the k+1 case".

And here, you are struggling with justifying the steps of the proof or seeing why they imply the conclusion:
MathDoofus wrote:
Meteoric wrote:Great! Then since k is either even or odd, we know that k+1 is odd (in the first case) or even (in the second case). That is, k+1 is either even or odd.

That's the induction step. We took a fact about k, and used it to demonstrate a fact about k+1.

Yes, but I don't understand how that's an example of proof by induction. I haven't shown anything for k or (k + 1), only for examples (here, 1) that I've selected at random.

which is exactly the same place you're stuck in the original problem, trying to follow the jump from step 2 to steps 3 or 4:
MathDoofus wrote:Still at Step 2 and trying figure out which steps come next, and why:

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

Can you help with that?

In the even/odd problem, the answers to your question are short English sentences. In the other problem, they're large algebraic expressions that can be hard to tell apart. But you're hitting the same stumbling blocks in both, and I think if you figure them out in the even/odd problem, it will carry over to the other.
No, even in theory, you cannot build a rocket more massive than the visible universe.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

I'll just leave this here. It's the post I posted a page ago and was completely ignore by mathdofus. I ask that you read this post, if you hit a point you don't understand, write down what you don't understand on a piece of paper and continue reading, writing the points you don't understand. Then read it again and see if you can find answers to any of the points you didn't understand.

Demki wrote:It's a proof by induction of the statement "every natural number n is either even or odd"

Another, simpler(and pretty trivial) proof by induction would be "every positive natural number n is divisible by 1"

To prove that by induction, we follow the basic steps of induction:

Base case: 1 is trivially divisible by 1(you can check your calculator if you want)

Inductive step: we want to prove the following statement "if k is divisible by 1 then (k+1) is divisible by 1"
We prove that statement by assuming that k is divisible by 1 and showing that k+1 is divisible by 1:
1. k is divisible by 1 (premise)
2. 1 is divisible by 1 (base case)
3. The sum of 2 numbers divisible by some integer m is also divisible by m (you could try to prove this, if you want I'll post a proof of that, it is simple algebra with no induction)
4. k+1 is divisible by 1 (follows from statements 1, 2 and 3)
So we've shown that statement 1 implies statement 4, that is, we've shown "if k is divisible by 1 then (k+1) is divisible by 1"

We've shown both the base case and the inductive step, therefore we've produced a valid proof by induction that every positive natural number is divisible by 1. (Provided any positive natural number I can build a finite "ladder" from the base case and inductive steps to show that number is divisible by 1)

As others have said, I strongly suggest you leave the problem of the sum of the first n numbers alone for now, and go study algebra and logic and get a good grasp on both. Yes the problem isn't particularily hard, but what you are doing here is trying to tighten a screw with a broken screwdriver.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

Demki, your example is a good one, and may sidestep issues about "or" statements in proofs.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:Demki, your example is a good one, and may sidestep issues about "or" statements in proofs.

I am far too invested in the original problem to drop it. Although I appreciate that others are trying to direct me to alternative problems, I do not yet have the instincts or insight to be able to solve those. I would like to stick with this problem.

Zohar
COMMANDER PORN
Posts: 8361
Joined: Fri Apr 27, 2007 8:45 pm UTC
Location: Denver

### Re: Mathematical Induction - Introductory Question

MathDoofus, you are writing an enormous amount of posts in two very active threads on two rather different topics. Personally, I don't know if you're taking the time to take everything that's being said to you and process it. You can, of course, continue in this manner, but my suggestion to you is to take a short break, and try to find some other example of induction online, and slowly work your way through them. It really sounds to me like you need to take a breather. Again, this is just a suggestion to how I think you may understand these topics better.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."

Not how I say my name

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Zohar wrote:MathDoofus, you are writing an enormous amount of posts in two very active threads on two rather different topics. Personally, I don't know if you're taking the time to take everything that's being said to you and process it. You can, of course, continue in this manner, but my suggestion to you is to take a short break, and try to find some other example of induction online, and slowly work your way through them. It really sounds to me like you need to take a breather. Again, this is just a suggestion to how I think you may understand these topics better.

That is a fair suggestion. I have looked for other examples online but the original example appears to be the simplest (other examples involve things like exponents, which I'm less comfortable with, or they're so minimalist (like the even-odd problem) that I'm confused about how induction is a useful way to prove those propositions).

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

Fun fact: the top answer to the question "how to prove that every integer is either even or odd" on math stackexchange is proof by induction.
https://math.stackexchange.com/question ... ven-or-odd

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Demki wrote:Fun fact: the top answer to the question "how to prove that every integer is either even or odd" on math stackexchange is proof by induction.
https://math.stackexchange.com/question ... ven-or-odd

I recognize that such a proof is possible (various folks have shown it to me in this thread) but it's so different in kind from the original problem that it doesn't feel like induction is a useful way of analyzing the even-odd problem.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

Proof by induction is usually useful when you want to prove some statement about all integers greater than or equal to some starting value. The original problem in this thread has the statement "1+2+3+...+(n-1)+n=n(n+1)/2"
The even-odd problem has the statement "n is even or n is odd"
The divisible by 1 problem has the statement "n is divisible by 1"

All of which share the fact that n is allowed to be any integer greater than or equal to some starting value(in all these cases we would probably take the starting value to be 1)

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5493
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, MA
Contact:

### Re: Mathematical Induction - Introductory Question

It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means.
LE4dGOLEM: What's a Doug?
Noc: A larval Doogly. They grow the tail and stinger upon reaching adulthood.

Keep waggling your butt brows Brothers.
Or; Is that your eye butthairs?

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

doogly wrote:It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means.

I would agree with that, but the problem with the even-odd example is that it doesn't (at least in my view) align well with the structure of a proof by induction (one example is that it requires or-statement that have no extra truth value).

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:
doogly wrote:It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means.

I would agree with that, but the problem with the even-odd example is that it doesn't (at least in my view) align well with the structure of a proof by induction (one example is that it requires or-statement that have no extra truth value).

Why not, we just showed the proof by induction of that? What do you mean by "or-statement that have no extra truth value"?

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Demki wrote::arrow:
MathDoofus wrote:
doogly wrote:It's pedagogically useful. It is nice to practice proof by induction if you do not understand induction by using it to prove things which you can already understand and prove by another means.

I would agree with that, but the problem with the even-odd example is that it doesn't (at least in my view) align well with the structure of a proof by induction (one example is that it requires or-statement that have no extra truth value).

Why not, we just showed the proof by induction of that? What do you mean by "or-statement that have no extra truth value"?

As a beginner, a proof by induction does not seem like a profitable way to show that every natural number must be even or odd. I think I've explained why that's so earlier in this thread, but I'll repeat that (1) there's no obvious (to a neophyte) way to make the even-odd question fit into the mold of an inductive proof and (2) the background knowledge regarding even and odd numbers serves as a distraction.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

What background knowledge? Do you have some other proof that every integer is either even or odd?
Remember that "n is even" means "there exists m such that n=2m" and "n is odd" means "there exists m such that n=2m+1"
Did you ever prove the statement "every positive integer is either even or odd" before this thread, or were you just taking that on "I know that's true"?

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Demki wrote:What background knowledge? Do you have some other proof that every integer is either even or odd?
Remember that "n is even" means "there exists m such that n=2m" and "n is odd" means "there exists m such that n=2m+1"
Did you ever prove the statement "every positive integer is either even or odd" before this thread, or were you just taking that on "I know that's true"?

I know that all even positive integers are divisible by 2 with no remainder. I know that everything else is not divisible by 2 with no remainder, so those must be the odd integers. When those two statements (propositions) are combined, there's simply no room for positive integers of any other flavor. So it's basically a proof-by-contradiction such that, if you posited that there existed some positive integer that's neither even nor odd, you couldn't fit that integer into the space of positive integers because even and odd integers occupy the whole space (e.g., any plus-1 step leads to an even or odd integer, and nothing else, as far up the ladder as you want to go).

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Demki wrote:The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification.

I have to start somewhere. By necessity, because "even" and "odd" are labels that human beings place on integers having certain properties, I described (what I believe) an even integer is. What else do you want? Your criticism seems misplaced.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:
Demki wrote:The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification.

I have to start somewhere. By necessity, because "even" and "odd" are labels that human beings place on integers having certain properties, I described (what I believe) an even integer is. What else do you want? Your criticism seems misplaced.

My criticism isn't of your first sentence, it is of the second sentence you wrote without any justification.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Demki wrote:
MathDoofus wrote:
Demki wrote:The first sentence you wrote just reiterates the definition of an even number. You gave no justification for why every integer that isn't even to be odd, since odd means 1 greater than an even number. The proof by induction provides such justification.

I have to start somewhere. By necessity, because "even" and "odd" are labels that human beings place on integers having certain properties, I described (what I believe) an even integer is. What else do you want? Your criticism seems misplaced.

My criticism isn't of your first sentence, it is of the second sentence you wrote without any justification.

Let's consider the only possibilities. I can show that, for any positive integer k, that it's either divisible by two cleanly or not. For those numbers that aren't cleanly divisible by two, I'll call those the "odd" numbers. Then let's consider the smallest increment involving positive integers (the plus-1) increment. Any arbitrarily chosen starting positive integers will either by cleanly divisible by two or not. For those that are cleanly divisible by two, the plus-1 increment leaves you at an odd number. For those that aren't cleanly divisible by two, the plus-1 increment leaves you at even number. Because all the rungs (increments) can be accounted for in this way, there's simply no way that a non-even and non-odd positive integer could exist.

Meteoric
Posts: 333
Joined: Wed Nov 23, 2011 4:43 am UTC

### Re: Mathematical Induction - Introductory Question

Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers.
No, even in theory, you cannot build a rocket more massive than the visible universe.

MathDoofus
Posts: 252
Joined: Fri Jan 02, 2015 2:01 pm UTC

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers.

But my argument still contains an assumption that I'd need to build out (I think), which is that every positive integer is either cleanly divisible by two or not. I'm not sure how I'd deal with in a proof by induction.

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:
Meteoric wrote:Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers.

But my argument still contains an assumption that I'd need to build out (I think), which is that every positive integer is either cleanly divisible by two or not. I'm not sure how I'd deal with in a proof by induction.

So instead of using the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number not divisible by 2
Use the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number one greater than a number cleanly divisible by 2

This way you are tasked to prove that every integer that isn't even is odd.
The steps are basically the same as what you said earlier, just with a bit more justification as to why "an odd number + 1 is even"

I mean, clearly if we replace the 2s in these definitions with a 3, then the first set of definition still cover every integer, yet the second set doesn't (every integer of the form 3n+2 is missing)

And this is why it is important to state your definitions clearly. (as I wrote in my post)
Demki wrote:What background knowledge? Do you have some other proof that every integer is either even or odd?
Remember that "n is even" means "there exists m such that n=2m" and "n is odd" means "there exists m such that n=2m+1"
Did you ever prove the statement "every positive integer is either even or odd" before this thread, or were you just taking that on "I know that's true"?

Return to “Mathematics”

### Who is online

Users browsing this forum: No registered users and 17 guests