Mathematical Induction  Introductory Question
Moderators: gmalivuk, Moderators General, Prelates
Re: Mathematical Induction  Introductory Question
Now you've got the lefthand side from the k+1 case, but the righthand side from the k case.
No, even in theory, you cannot build a rocket more massive than the visible universe.
Re: Mathematical Induction  Introductory Question
No, sorry, that's still wrong. Carefully consider this, this is the root of what we're trying to get to.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."
Not how I say my name
SecondTalon: "Still better looking than Jesus."
Not how I say my name

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Zohar wrote:No, sorry, that's still wrong. Carefully consider this, this is the root of what we're trying to get to.
Then I'm not sure about the error. I believe that I want to show that adding the k and (k + 1) case to the lefthand side still equals the righthand siden(n + 1)/2of the original equation.
Re: Mathematical Induction  Introductory Question
You're talking about how to get to the goal. Before you can do that, you have to know what the goal is.
The k+1 case is not inherently connected to the k case. You can state the k+1 case, on its own, without reference to anything else. When you do that, what is the equation?
The k+1 case is not inherently connected to the k case. You can state the k+1 case, on its own, without reference to anything else. When you do that, what is the equation?
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:You're talking about how to get to the goal. Before you can do that, you have to know what the goal is.
The k+1 case is not inherently connected to the k case. You can state the k+1 case, on its own, without reference to anything else. When you do that, what is the equation?
Not sure what you mean.
The (k + 1) case on its own would be:
1 + 2 + 3 + ... + (k + 1) = k(k + 1)/2
Re: Mathematical Induction  Introductory Question
Again, your righthand side is incorrect. Go back to the original question (using n), and replace n's with (k+1). You have not done that.
Mighty Jalapeno: "See, Zohar agrees, and he's nice to people."
SecondTalon: "Still better looking than Jesus."
Not how I say my name
SecondTalon: "Still better looking than Jesus."
Not how I say my name

 Posts: 389
 Joined: Wed Sep 21, 2011 3:44 am UTC
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:The (k + 1) case on its own would be:
1 + 2 + 3 + ... + (k + 1) = k(k + 1)/2
Not quite. Remember, the generic "n" case is:
1 + 2 + 3 + ... + n = n(n + 1)/2
The (k + 1) case is what you would get if you put "(k + 1)" in place of every single "n" above. What you've done is put "(k + 1)" in place of the "n" on the left side of the equals sign, but you have put "k" in place of each "n" on the right side of the equals sign.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
arbiteroftruth wrote:MathDoofus wrote:The (k + 1) case on its own would be:
1 + 2 + 3 + ... + (k + 1) = k(k + 1)/2
Not quite. Remember, the generic "n" case is:
1 + 2 + 3 + ... + n = n(n + 1)/2
The (k + 1) case is what you would get if you put "(k + 1)" in place of every single "n" above. What you've done is put "(k + 1)" in place of the "n" on the left side of the equals sign, but you have put "k" in place of each "n" on the right side of the equals sign.
Gotcha.
Here's my attempt at summing up what I'm trying to show:
1 + 2 + 3 + ... + n = n(n + 1)/2 = 1 + 2 + 3 + ... + k = k(k + 1)/2 = 1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
Is that correct?
Re: Mathematical Induction  Introductory Question
No, you're only trying to show the last part:
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
The preceding equations are not what you're trying to show. Moreover, they are false: for example, the sum of 1 through k is certainly not equal to the sum of 1 through k+1. It seems like you might be using an equals sign to indicate "and now we move to the next step", but an equals sign means equality. If you need to use a symbol to indicate the next step, use an arrow or something other than an equals sign.
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
The preceding equations are not what you're trying to show. Moreover, they are false: for example, the sum of 1 through k is certainly not equal to the sum of 1 through k+1. It seems like you might be using an equals sign to indicate "and now we move to the next step", but an equals sign means equality. If you need to use a symbol to indicate the next step, use an arrow or something other than an equals sign.
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:No, you're only trying to show the last part:
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
The preceding equations are not what you're trying to show. Moreover, they are false: for example, the sum of 1 through k is certainly not equal to the sum of 1 through k+1. It seems like you might be using an equals sign to indicate "and now we move to the next step", but an equals sign means equality. If you need to use a symbol to indicate the next step, use an arrow or something other than an equals sign.
Then I'm lost again. I give up.
I don't know how to connect up the k case and the (k + 1) case if what you're saying is true. I give up. I am simply too stupid to grasp this.
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:Then I'm lost again.
That's OK. That's how math goes: you are constantly lost, all the time.
Before, you wrote that the k+1 case was
1 + ... + (k+1) = k(k+1)/2
This wasn't structurally wrong, it was the right kind of statement. However, you had an error:
1 + ... + (k+1) = (k+1)(k+2)/2
There is no need to introduce three additional equals signs, nor the variable n, nor a bunch of new sums. You just needed to correct the righthand side, by plugging in (k+1) instead of k.
I give up.
I don't know how to connect up the k case and the (k + 1) case if what you're saying is true. I give up.
I am sorry to hear that.
We are happy to help you here and walk you through things. But I have to agree with gmalivuk earlier in this thread: the reason you're having difficulty is that you're not really ready to be working on this problem.
This step that we're examining right now is "plugging a value into an equation", and has nothing to do with connecting one case to another. We've also run into trouble with algebra, with equations, with conditionals, with how proofs are written, with what assumptions are. Induction per se is a sideshow in this thread. Any one of these topics is not too hard to explain, by itself. But instead, we keep leaping around trying to understand ten interlocking parts, and there's no time to let any one of them sink in. So by the time we get to the third part, the first has stopped making sense, and we can't get anywhere.
If you could nail down all of those topics separately  and they are much easier to work on separately  then I think you would come back and find that induction was straightforward, or at most that you got stuck on one thing. Instead, we have gotten stuck on every single component of the proof.
Last edited by Meteoric on Tue May 02, 2017 7:04 pm UTC, edited 3 times in total.
No, even in theory, you cannot build a rocket more massive than the visible universe.
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:No, you're only trying to show the last part:
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
The preceding equations are not what you're trying to show. Moreover, they are false: for example, the sum of 1 through k is certainly not equal to the sum of 1 through k+1. It seems like you might be using an equals sign to indicate "and now we move to the next step", but an equals sign means equality. If you need to use a symbol to indicate the next step, use an arrow or something other than an equals sign.
Yep, Meteoric's right. You don't want to think of
MathDoofus wrote:1 + 2 + 3 + ... + n = n(n + 1)/2 = 1 + 2 + 3 + ... + k = k(k + 1)/2 = 1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2
as equalities, because they may not, in general, be equal. But you're on a sortof right track. Split these statements up.
1 + 2 + 3 + ... + n = n(n + 1)/2 (equation 0)
This is the general statement you're trying to prove.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
This is the first part of the induction step. This is the kcase, or equivalently, this is the case of the equation above (equation 0) with n = k (substitute k anywhere you see n)
k is just a placeholder for some positive integer.
This is what you assume to be true in order to prove the next step.
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2 (equation 2)
This is the second part of the induction step. It's equation 0 with n replaced by (k+1)  it's the case of n = k+1.
What you need to show is that if we assume equation 1 is true, we can get equation 2 from it. How do we do that?
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
1 + 2 + 3 + ... + k + (k+1)= k(k + 1)/2 + (k+1) (equation 3)
The left hand side of equation 3 is exactly the same as the left hand side of equation 2
If two things are equal to the same thing, they must be equal to each other. So if the right hand sides of equation 2 and 3 are equal to the same thing, they should be equal to each other:
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
If you can show this to be true, you're done, because this proves that if equation 1 is true, equation 2 must be true as well.
Couple that with a base case (n = 1), and you get n = 2, n = 3, n = 4 ... all positive integers.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:This is what you assume to be true in order to prove the next step.
1 + 2 + 3 + ... (k + 1) = (k +1)((k + 1) + 1)/2 (equation 2)
This is the second part of the induction step. It's equation 0 with n replaced by (k+1)  it's the case of n = k+1.
What you need to show is that if we assume equation 1 is true, we can get equation 2 from it. How do we do that?
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
1 + 2 + 3 + ... + k + (k+1)= k(k + 1)/2 + (k+1) (equation 3)
The left hand side of equation 3 is exactly the same as the left hand side of equation 2
If two things are equal to the same thing, they must be equal to each other. So if the right hand sides of equation 2 and 3 are equal to the same thing, they should be equal to each other:
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
If you can show this to be true, you're done, because this proves that if equation 1 is true, equation 2 must be true as well.
Couple that with a base case (n = 1), and you get n = 2, n = 3, n = 4 ... all positive integers.
I think that I understand steps 0 (what we're ultimately trying to show) and 1 (the k case, as an arbitrary replacement for n).
Equation 1 makes sense; that's implementing k in place of n.
Why, though, do we add (k + 1) to both sides of Equation 1?
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
What's the difference between the kcase and the (k+1)case?
It's the same as the answer to: what is the difference between the left hand side of equation 1 and the left hand side of equation 2?
Answer: (k+1)
So what we need to do is use the kcase to get to the (k+1) case. That's important  the idea of "if the kcase is true, then the (k+1)case is true" is only useful if we can link the kcase to the (k+1)case. How do we get from the kcase to the (k+1)case? Add (k+1). And since we're talking about equalities, we have to add it to both sides.
It's the same as the answer to: what is the difference between the left hand side of equation 1 and the left hand side of equation 2?
Answer: (k+1)
So what we need to do is use the kcase to get to the (k+1) case. That's important  the idea of "if the kcase is true, then the (k+1)case is true" is only useful if we can link the kcase to the (k+1)case. How do we get from the kcase to the (k+1)case? Add (k+1). And since we're talking about equalities, we have to add it to both sides.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:What's the difference between the kcase and the (k+1)case?
It's the same as the answer to: what is the difference between the left hand side of equation 1 and the left hand side of equation 2?
Answer: (k+1)
So what we need to do is use the kcase to get to the (k+1) case. That's important  the idea of "if the kcase is true, then the (k+1)case is true" is only useful if we can link the kcase to the (k+1)case. How do we get from the kcase to the (k+1)case? Add (k+1). And since we're talking about equalities, we have to add it to both sides.
But, when I did that before, someone said it was wrong. So do I simply add (k + 1) to both sides or do I also substitute (k + 1) in place of every single reference to k? That's what I'm currently pondering.
Re: Mathematical Induction  Introductory Question
If you want to learn mathematical induction without this cumbersome triangle problem, could you try the problem I posted before? It doesn't have algebra, "just" logic.
Actually, try Meteoric's problem first: (paraphrased) using induction, prove that every number starting at 1 is even or odd.
Remember that, if you have an odd number, the next number is even.
I'd like to give some example proofs, but all examples I can think of are either too trivial (i.e. a direct proof is more intuitive, like the evenorodd problem) or require algebra.
Actually, try Meteoric's problem first: (paraphrased) using induction, prove that every number starting at 1 is even or odd.
Remember that, if you have an odd number, the next number is even.
I'd like to give some example proofs, but all examples I can think of are either too trivial (i.e. a direct proof is more intuitive, like the evenorodd problem) or require algebra.
Spoiler:
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:But, when I did that before, someone said it was wrong.
When you did that before, we said it was not the final goal. It was absolutely, incontrovertibly correct  but you were trying to figure out where the proof should end, and that's not the last step.
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Flumble wrote:If you want to learn mathematical induction without this cumbersome triangle problem, could you try the problem I posted before? It doesn't have algebra, "just" logic.
Actually, try Meteoric's problem first: (paraphrased) using induction, prove that every number starting at 1 is even or odd.
Remember that, if you have an odd number, the next number is even.
I'd like to give some example proofs, but all examples I can think of are either too trivial (i.e. a direct proof is more intuitive, like the evenorodd problem) or require algebra.Spoiler:
Thank you for that suggestion, but I need to nail this one down first. I doubt that I'm going to have any insight regarding how induction can be used to solve any particular problem. I don't even know what form the base cases would take for your evenandodd suggestion; that seems totally foreign to me, like proving that Pluto tastes better than my dress shoes.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:MathDoofus wrote:But, when I did that before, someone said it was wrong.
When you did that before, we said it was not the final goal. It was absolutely, incontrovertibly correct  but you were trying to figure out where the proof should end, and that's not the last step.
So which is it, and why? Do I add (k + 1) to both sides at the same time that I replace all instances of k with (k + 1)? And why? That's what I'm trying to figure out at the moment.
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
Do not substitute k+1 for k. Doing that without knowing exactly why you're doing it will lead you to a wrong answer.
So go back to this point:
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
Start with equation 1.
1 + 2 + 3 + ... + k + (k+1) = k(k + 1)/2 + (k+1) (equation 1, with k+1 added to both sides)
1 + 2 + 3 + ... + k + (k+1) = (k +1)((k + 1) + 1)/2 (equation 2, which comes from equation 0, with n = k+1)
If what we're trying to prove is really true, both equalities above are true.
The left hand sides of those equations are exactly the same, so they're equal. Thus, the righthand sides should be equal.
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
Try taking it from here and show us your steps.
So go back to this point:
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
Start with equation 1.
1 + 2 + 3 + ... + k + (k+1) = k(k + 1)/2 + (k+1) (equation 1, with k+1 added to both sides)
1 + 2 + 3 + ... + k + (k+1) = (k +1)((k + 1) + 1)/2 (equation 2, which comes from equation 0, with n = k+1)
If what we're trying to prove is really true, both equalities above are true.
The left hand sides of those equations are exactly the same, so they're equal. Thus, the righthand sides should be equal.
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
Try taking it from here and show us your steps.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:Do not substitute k+1 for k. Doing that without knowing exactly why you're doing it will lead you to a wrong answer.
So go back to this point:
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
Start with equation 1.
1 + 2 + 3 + ... + k + (k+1) = k(k + 1)/2 + (k+1) (equation 1, with k+1 added to both sides)
1 + 2 + 3 + ... + k + (k+1) = (k +1)((k + 1) + 1)/2 (equation 2, which comes from equation 0, with n = k+1)
If what we're trying to prove is really true, both equalities above are true.
The left hand sides of those equations are exactly the same, so they're equal. Thus, the righthand sides should be equal.
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
Try taking it from here and show us your steps.
I'll try taking it from there (give me a couple minutes), thank you.
But I'm now getting confused about whyafter equation 1I want to add (k + 1) to both sides. And how that relates to substituting (k + 1) for k. Can you please go over those steps in detail?
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:Meteoric wrote:MathDoofus wrote:But, when I did that before, someone said it was wrong.
When you did that before, we said it was not the final goal. It was absolutely, incontrovertibly correct  but you were trying to figure out where the proof should end, and that's not the last step.
So which is it, and why? Do I add (k + 1) to both sides at the same time that I replace all instances of k with (k + 1)? And why? That's what I'm trying to figure out at the moment.
The goal is to end up with an equation where it looks like all instances of k+1 have been replaced with k. One of the steps you use to get there is adding (k+1) to both sides.
Let's look back to this from earlier:
Meteoric wrote:
 1+2+...+k = k(k+1)/2 [TRUE BECAUSE: assumption AKA premise]
 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) [TRUE BECAUSE: add (k+1) to both sides of #1]
 k(k+1)/2 + (k+1) = (k+1)(k+2)/2 [TRUE BECAUSE: do some algebra]
 1+2+...+k+(k+1) = (k+1)(k+2)/2 [TRUE BECAUSE: transitivity on #2 and #3]
Step 2 is where we added (k+1) to both sides. This was a crucial step, but not the only step. Step 4 is where we end up, with an equation in terms of (k+1), instead of in terms of k.
Then you asked
MathDoofus wrote:Now I'm stuck; I'm not exactly sure what the next step should be after adding (k + 1) to both sides of the equation.
So we were talking about what happens AFTER step 2. From there, you are very close to the goal  but you have to know what the goal IS before you can figure out how to get there.
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:So we were talking about what happens AFTER step 2. From there, you are very close to the goal  but you have to know what the goal IS before you can figure out how to get there.
That's exactly itafter getting to step 1, which involves writing out the k case and assuming that it's trueI don't know how the next two steps relate to each other, or why each is necessary. Can you explain that?
To recap, I'm here:
Step 0 (what I ultimately hope to prove)  For all positive integers, 1 + 2 + 3 + ... + n = n(n + 1)/2
Step 1 (the k case, which I assume)  1 + 2 + 3 + ... + k = k(k +1)/2
What is next, and why? And what's immediately after that, and why? Those are the questions that I'm struggling with now.
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:WibblyWobbly wrote:Do not substitute k+1 for k. Doing that without knowing exactly why you're doing it will lead you to a wrong answer.
So go back to this point:
Start with equation 1.
1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
Add (k+1) to both sides:
Start with equation 1.
1 + 2 + 3 + ... + k + (k+1) = k(k + 1)/2 + (k+1) (equation 1, with k+1 added to both sides)
1 + 2 + 3 + ... + k + (k+1) = (k +1)((k + 1) + 1)/2 (equation 2, which comes from equation 0, with n = k+1)
If what we're trying to prove is really true, both equalities above are true.
The left hand sides of those equations are exactly the same, so they're equal. Thus, the righthand sides should be equal.
(k +1)((k + 1) + 1)/2 = k(k + 1)/2 + (k+1)
Try taking it from here and show us your steps.
I'll try taking it from there (give me a couple minutes), thank you.
But I'm now getting confused about whyafter equation 1I want to add (k + 1) to both sides. And how that relates to substituting (k + 1) for k. Can you please go over those steps in detail?
Because you need to use the kcase (assume it is true) to get to the (k+1) case.
If the sum of the first k positive integers is 1 + 2 + 3 + ... + k, what is the sum of the first (k+1) positive integers? It's the sum of the first k positive integers ... plus k+1.
1 + 2 + 3 + ... + k+1 = 1 + 2 + 3 + ... + k + k+1 = (1 + 2 + 3 + ... + k) + k+1
So you get to the (k+1)case by starting with the kcase and adding k+1.
 doogly
 Dr. The Juggernaut of Touching Himself
 Posts: 5338
 Joined: Mon Oct 23, 2006 2:31 am UTC
 Location: Somerville, MA
 Contact:
Re: Mathematical Induction  Introductory Question
MathDoofus wrote: So do I simply add (k + 1) to both sides or do I also substitute (k + 1) in place of every single reference to k? That's what I'm currently pondering.
The thing you are trying to prove is that these both amount to the same thing, is one way to look at it. You have to show that they're equivalent.
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?
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?

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:Because you need to use the kcase (assume it is true) to get to the (k+1) case.
If the sum of the first k positive integers is 1 + 2 + 3 + ... + k, what is the sum of the first (k+1) positive integers? It's the sum of the first k positive integers ... plus k+1.
1 + 2 + 3 + ... + k+1 = 1 + 2 + 3 + ... + k + k+1 = (1 + 2 + 3 + ... + k) + k+1
Then I'm hopelessly confused. Why is it that I add (k + 1) to both sides? And how's the substitution step relate to that? I need an explanation of that because the more I study this, the less I'm sure of!

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
doogly wrote:MathDoofus wrote: So do I simply add (k + 1) to both sides or do I also substitute (k + 1) in place of every single reference to k? That's what I'm currently pondering.
The thing you are trying to prove is that these both amount to the same thing, is one way to look at it. You have to show that they're equivalent.
I took that tack before and someone said it was wrong (see my string with all of the equals signs).
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:WibblyWobbly wrote:Because you need to use the kcase (assume it is true) to get to the (k+1) case.
If the sum of the first k positive integers is 1 + 2 + 3 + ... + k, what is the sum of the first (k+1) positive integers? It's the sum of the first k positive integers ... plus k+1.
1 + 2 + 3 + ... + k+1 = 1 + 2 + 3 + ... + k + k+1 = (1 + 2 + 3 + ... + k) + k+1
Then I'm hopelessly confused. Why is it that I add (k + 1) to both sides? And how's the substitution step relate to that? I need an explanation of that because the more I study this, the less I'm sure of!
Do you understand why you would add (k+1) to 1 + 2 + 3 + ... + k ?
(Because it takes you from (sum of first k positive integers) to (sum of first k+1 positive integers))
Last edited by WibblyWobbly on Tue May 02, 2017 7:35 pm UTC, edited 1 time in total.
Re: Mathematical Induction  Introductory Question
1 + ... + k = k(k+1)/2
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
What steps could go in the [???] box to make this a valid proof? Well, the lefthand sides sure look similar, yeah? We just need an extra (k+1) term. So let's add that in.
1 + ... + k = k(k+1)/2
1 + ... + k + (k+1) = k(k+1)/2 + (k+1) [by adding (k+1) to both sides]
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
Now, what else can go in the [???] box to get you the rest of the way? At step 2, the lefthand side is already what we want. So everything of interest must happen on the righthand side. What can you do with the righthand side of step 2? Could you simplify it?
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
What steps could go in the [???] box to make this a valid proof? Well, the lefthand sides sure look similar, yeah? We just need an extra (k+1) term. So let's add that in.
1 + ... + k = k(k+1)/2
1 + ... + k + (k+1) = k(k+1)/2 + (k+1) [by adding (k+1) to both sides]
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
Now, what else can go in the [???] box to get you the rest of the way? At step 2, the lefthand side is already what we want. So everything of interest must happen on the righthand side. What can you do with the righthand side of step 2? Could you simplify it?
No, even in theory, you cannot build a rocket more massive than the visible universe.
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:doogly wrote:MathDoofus wrote: So do I simply add (k + 1) to both sides or do I also substitute (k + 1) in place of every single reference to k? That's what I'm currently pondering.
The thing you are trying to prove is that these both amount to the same thing, is one way to look at it. You have to show that they're equivalent.
I took that tack before and someone said it was wrong (see my string with all of the equals signs).
We need to show that the statements are equivalent, not that the numbers are equal.
1+1=2 and 2+2=4. These statements are equivalent, because you can easily prove one from the other. But 2 is not equal to 4.
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:1+1=2 and 2+2=4. These statements are equivalent, because you can easily prove one from the other. But 2 is not equal to 4.
I didn't know that there's a distinction between equivalent and equal. That's a useful tidbit. There are probably a lot of implicit assumptions in the various explanations of this process that aren't being made explicit. That's part of the reason why I feel like I'm experiencing whiplash when I post something and it's (rightly) criticized as wrong or, at best, incomplete.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:1 + ... + k = k(k+1)/2
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
What steps could go in the [???] box to make this a valid proof? Well, the lefthand sides sure look similar, yeah? We just need an extra (k+1) term. So let's add that in.
1 + ... + k = k(k+1)/2
1 + ... + k + (k+1) = k(k+1)/2 + (k+1) [by adding (k+1) to both sides]
[???]
1 + ... + k + (k+1) = (k+1)(k+2)/2
Now, what else can go in the [???] box to get you the rest of the way? At step 2, the lefthand side is already what we want. So everything of interest must happen on the righthand side. What can you do with the righthand side of step 2? Could you simplify it?
I don't understand that question, sorry. Are you suggesting that the lefthand sides are always supposed to be the same?

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:MathDoofus wrote:WibblyWobbly wrote:Because you need to use the kcase (assume it is true) to get to the (k+1) case.
If the sum of the first k positive integers is 1 + 2 + 3 + ... + k, what is the sum of the first (k+1) positive integers? It's the sum of the first k positive integers ... plus k+1.
1 + 2 + 3 + ... + k+1 = 1 + 2 + 3 + ... + k + k+1 = (1 + 2 + 3 + ... + k) + k+1
Then I'm hopelessly confused. Why is it that I add (k + 1) to both sides? And how's the substitution step relate to that? I need an explanation of that because the more I study this, the less I'm sure of!
Do you understand why you would add (k+1) to 1 + 2 + 3 + ... + k ?
(Because it takes you from (sum of first k positive integers) to (sum of first k+1 positive integers))
Yes, I think that I understand that, at least in part. I doat some pointhave to connect the k case and the (k + 1) case in some way. But why is it that I have to (I think) substitute (k + 1) down the line? Can you explain how those are related?
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:WibblyWobbly wrote:MathDoofus wrote:WibblyWobbly wrote:Because you need to use the kcase (assume it is true) to get to the (k+1) case.
If the sum of the first k positive integers is 1 + 2 + 3 + ... + k, what is the sum of the first (k+1) positive integers? It's the sum of the first k positive integers ... plus k+1.
1 + 2 + 3 + ... + k+1 = 1 + 2 + 3 + ... + k + k+1 = (1 + 2 + 3 + ... + k) + k+1
Then I'm hopelessly confused. Why is it that I add (k + 1) to both sides? And how's the substitution step relate to that? I need an explanation of that because the more I study this, the less I'm sure of!
Do you understand why you would add (k+1) to 1 + 2 + 3 + ... + k ?
(Because it takes you from (sum of first k positive integers) to (sum of first k+1 positive integers))
Yes, I think that I understand that, at least in part. I doat some pointhave to connect the k case and the (k + 1) case in some way. But why is it that I have to (I think) substitute (k + 1) down the line? Can you explain how those are related?
Exactly  adding k+1 to both sides connects the kcase to the (k+1)case.
Where do you think you need to substitute (k+1) down the line?

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:Where do you think you need to substitute (k+1) down the line?
Once I relate (or incorporate, or do some mathverb) k and (k + 1) (see below)
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) #I added (k + 1) to the righthand side as well because that's what algebra rules require.
Beyond that, I think that at some point I'm required to substitute (k + 1) for every instance of k. I don't know why that's so, but I think that I have to do it.
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:I don't understand that question, sorry. Are you suggesting that the lefthand sides are always supposed to be the same?
No. We have lost sight of the goal again. This is not your fault: it is impossible to keep your eye on the ball when we constantly have pagelong detours onto other topics.
So seriously, I really absolutely cannot stress this strongly enough. Stop working on this problem. Set it aside. Work on some of the subtopics that have come up.
Practice your algebra, until you are absolutely 100% comfortable with taking one equation and manipulating it into a different equation.
Write some proofs of conditionals.
Practice some induction that doesn't involve large expressions, like the even/odd problem.
Feel free to ask questions about those, but work on them in isolation, with smaller problems than this. If you don't know how to practice them, we can provide you with practice problems, or refer you to online resources.
Once you have those down, come back to this problem. It will be SO much easier, I promise.
No, even in theory, you cannot build a rocket more massive than the visible universe.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
Meteoric wrote:MathDoofus wrote:I don't understand that question, sorry. Are you suggesting that the lefthand sides are always supposed to be the same?
No. We have lost sight of the goal again. This is not your fault: it is impossible to keep your eye on the ball when we constantly have pagelong detours onto other topics.
So seriously, I really absolutely cannot stress this strongly enough. Stop working on this problem. Set it aside. Work on some of the subtopics that have come up.
Practice your algebra, until you are absolutely 100% comfortable with taking one equation and manipulating it into a different equation.
Write some proofs of conditionals.
Practice some induction that doesn't involve large expressions, like the even/odd problem.
Feel free to ask questions about those, but work on them in isolation, with smaller problems than this. If you don't know how to practice them, we can provide you with practice problems, or refer you to online resources.
Once you have those down, come back to this problem. It will be SO much easier, I promise.
I am so invested in this one that I can't reasonably stop working on it now. And the evenodd problem strikes me as even harder than this one (in fact, the evenodd problem looks like it'd require two separate lines of induction; one to deal with the evens and one to deal with the odds).
 WibblyWobbly
 Can't Get No
 Posts: 506
 Joined: Fri Apr 05, 2013 1:03 pm UTC
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:WibblyWobbly wrote:Where do you think you need to substitute (k+1) down the line?
Once I relate (or incorporate, or do some mathverb) k and (k + 1) (see below)
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) #I added (k + 1) to the righthand side as well because that's what algebra rules require.
Beyond that, I think that at some point I'm required to substitute (k + 1) for every instance of k. I don't know why that's so, but I think that I have to do it.
OK, I see. The answer is that you don't have to substitute (k+1) for every instance of k. I think I might know where you're getting confused.
So what you have now is:
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)
You got this from the kcase, by adding (k+1) to both sides. What you want to show is that this is the same as the (k+1)case, i.e., that this is equivalent to substituting (k+1) for n in the original equation: 1 + 2 + 3 + ... + n = n(n+1)/2. That might be where you were getting confused.
1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1]/2
This is the (k+1)case. You got this by substituting (k+1) for n in the original equation: 1 + 2 + 3 + ... + n = n(n+1)/2.
So here's the logic now:
This is the kcase:
1 + 2 + 3 + ... + k = k(k + 1)/2
You connected the kcase and the (k+1)case by adding (k+1) to both sides.
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)
For this proof to work, the above equation needs to be equivalent to the (k+1)case:
1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1]/2
Well, we can see that the left hand sides of those two equations are equal. The way we prove that
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) is equivalent to 1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1]/2
is by showing that the right hand sides are the same:
k(k + 1)/2 + (k + 1) = [(k+1)((k+1)+1]/2
If that equality is true, then the (k+1)case is true whenever the kcase is true.

 Posts: 252
 Joined: Fri Jan 02, 2015 2:01 pm UTC
Re: Mathematical Induction  Introductory Question
WibblyWobbly wrote:For this proof to work, the above equation needs to be equivalent to the (k+1)case:
1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1]/2
Well, we can see that the left hand sides of those two equations are equal. The way we prove that
1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) is equivalent to 1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1]/2
is by showing that the right hand sides are the same:
k(k + 1)/2 + (k + 1) = [(k+1)((k+1)+1]/2
Yes, that may be the source of the confusion  so why is it that, when I plugged in (k + 1) to both sides, I wasn't actually writing the (k + 1) case? And what relationship does substituting (k + 1) for every instance of k have to (1) the k case (which is Step 1/Equation 1) and (2) the case where k and (k + 1) are related (which is Step 2/Equation 2)?
Re: Mathematical Induction  Introductory Question
MathDoofus wrote:I am so invested in this one that I can't reasonably stop working on it now.
You can, and I really recommend you do. I'm not telling you to give up, I am telling you to back up and get a running start.
And the evenodd problem strikes me as even harder than this one (in fact, the evenodd problem looks like it'd require two separate lines of induction; one to deal with the evens and one to deal with the odds).
It isn't harder, and it doesn't require that. That's why I'm telling you to work on it: you don't seem to currently know how to do it, so the process of solving it will teach you something.
No, even in theory, you cannot build a rocket more massive than the visible universe.
Who is online
Users browsing this forum: No registered users and 16 guests