## Mathematical Induction - Introductory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### Re: Mathematical Induction - Introductory Question

Now you've got the left-hand side from the k+1 case, but the right-hand side from the k case.
No, even in theory, you cannot build a rocket more massive than the visible universe.

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

### 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

MathDoofus
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 left-hand side still equals the right-hand side--n(n + 1)/2--of the original equation.

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

### 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?
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: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

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

### Re: Mathematical Induction - Introductory Question

Again, your right-hand 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

arbiteroftruth
Posts: 461
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.

MathDoofus
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?

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

### 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.
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: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.

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

### 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 right-hand 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 sort-of 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 k-case, 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?

1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
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.

MathDoofus
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?

1 + 2 + 3 + ... + k = k(k + 1)/2 (equation 1)
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 k-case 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?

So what we need to do is use the k-case to get to the (k+1) case. That's important - the idea of "if the k-case is true, then the (k+1)-case is true" is only useful if we can link the k-case to the (k+1)-case. How do we get from the k-case to the (k+1)-case? Add (k+1). And since we're talking about equalities, we have to add it to both sides.

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

### Re: Mathematical Induction - Introductory Question

WibblyWobbly wrote:What's the difference between the k-case 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?

So what we need to do is use the k-case to get to the (k+1) case. That's important - the idea of "if the k-case is true, then the (k+1)-case is true" is only useful if we can link the k-case to the (k+1)-case. How do we get from the k-case 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.

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

### 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 even-or-odd problem) or require algebra.
Spoiler:
One example proof that may or may not help (because it's so damn trivial):
Prove all numbers, starting at 5, are greater than 0.

Base case: n=5, since the problem asks for it. 5 is greater than 0 so it's true.
Inductive step: n=k. Assuming k is greater than 0, let's see if the next number n'=k+1 is also greater than 0. Well, since k+1 is greater than k, which is greater than 0, k+1 must also be greater than 0. (thereby proving that, if it holds for some k, it also holds for k+1)

With the two combined, you have now proven that all numbers 5 and up are greater than 0.

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

### 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.

MathDoofus
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 even-or-odd problem) or require algebra.
Spoiler:
One example proof that may or may not help (because it's so damn trivial):
Prove all numbers, starting at 5, are greater than 0.

Base case: n=5, since the problem asks for it. 5 is greater than 0 so it's true.
Inductive step: n=k. Assuming k is greater than 0, let's see if the next number n'=k+1 is also greater than 0. Well, since k+1 is greater than k, which is greater than 0, k+1 must also be greater than 0. (thereby proving that, if it holds for some k, it also holds for k+1)

With the two combined, you have now proven that all numbers 5 and up are greater than 0.

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 even-and-odd suggestion; that seems totally foreign to me, like proving that Pluto tastes better than my dress shoes.

MathDoofus
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:

1 + 2 + 3 + ... + k = k(k + 1)/2 (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 right-hand 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.

MathDoofus
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:

1 + 2 + 3 + ... + k = k(k + 1)/2 (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 right-hand 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 why--after equation 1--I 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?

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

### 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. 1+2+...+k = k(k+1)/2 [TRUE BECAUSE: assumption AKA premise]
2. 1+2+...+k+(k+1) = k(k+1)/2 + (k+1) [TRUE BECAUSE: add (k+1) to both sides of #1]
3. k(k+1)/2 + (k+1) = (k+1)(k+2)/2 [TRUE BECAUSE: do some algebra]
4. 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.

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.

MathDoofus
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 it--after getting to step 1, which involves writing out the k case and assuming that it's true--I 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:

1 + 2 + 3 + ... + k = k(k + 1)/2 (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 right-hand 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 why--after equation 1--I 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 k-case (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 k-case and adding k+1.

doogly
Dr. The Juggernaut of Touching Himself
Posts: 5520
Joined: Mon Oct 23, 2006 2:31 am UTC
Location: Lexington, 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?

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

### Re: Mathematical Induction - Introductory Question

WibblyWobbly wrote:Because you need to use the k-case (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!

MathDoofus
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 k-case (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.

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

### 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 left-hand 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 left-hand side is already what we want. So everything of interest must happen on the right-hand side. What can you do with the right-hand side of step 2? Could you simplify it?
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

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.

MathDoofus
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.

MathDoofus
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 left-hand 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 left-hand side is already what we want. So everything of interest must happen on the right-hand side. What can you do with the right-hand side of step 2? Could you simplify it?

I don't understand that question, sorry. Are you suggesting that the left-hand sides are always supposed to be the same?

MathDoofus
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 k-case (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 do--at some point--have 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 k-case (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 do--at some point--have 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 k-case to the (k+1)-case.
Where do you think you need to substitute (k+1) down the line?

MathDoofus
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 math-verb) k and (k + 1) (see below)

1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) #I added (k + 1) to the right-hand 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.

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

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:I don't understand that question, sorry. Are you suggesting that the left-hand 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 page-long 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.

MathDoofus
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 left-hand 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 page-long 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 even-odd problem strikes me as even harder than this one (in fact, the even-odd 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 math-verb) k and (k + 1) (see below)

1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) #I added (k + 1) to the right-hand 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 k-case, 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 k-case:
1 + 2 + 3 + ... + k = k(k + 1)/2

You connected the k-case 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 k-case is true.

MathDoofus
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)?

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

### 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 even-odd problem strikes me as even harder than this one (in fact, the even-odd 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 6 guests