### Re: Mathematical Induction - Introductory Question

Posted:

**Tue May 02, 2017 6:00 pm UTC**Now you've got the left-hand side from the k+1 case, but the right-hand side from the k case.

Forums for the webcomic xkcd.com

http://forums.xkcd.com/

Page **4** of **7**

Posted: **Tue May 02, 2017 6:00 pm UTC**

Now you've got the left-hand side from the k+1 case, but the right-hand side from the k case.

Posted: **Tue May 02, 2017 6:00 pm UTC**

No, sorry, that's still wrong. Carefully consider this, this is the root of what we're trying to get to.

Posted: **Tue May 02, 2017 6:02 pm UTC**

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.

Posted: **Tue May 02, 2017 6:05 pm UTC**

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?

Posted: **Tue May 02, 2017 6:05 pm UTC**

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

Posted: **Tue May 02, 2017 6:09 pm UTC**

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.

Posted: **Tue May 02, 2017 6:12 pm UTC**

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.

Posted: **Tue May 02, 2017 6:35 pm UTC**

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?

Posted: **Tue May 02, 2017 6:46 pm UTC**

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.

Posted: **Tue May 02, 2017 6:47 pm UTC**

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.

Posted: **Tue May 02, 2017 6:58 pm UTC**

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.

Posted: **Tue May 02, 2017 6:58 pm UTC**

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?

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.

Posted: **Tue May 02, 2017 7:06 pm UTC**

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?

Posted: **Tue May 02, 2017 7:10 pm UTC**

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?

Answer: (k+1)

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.

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

Posted: **Tue May 02, 2017 7:12 pm UTC**

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?

Answer: (k+1)

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.

Posted: **Tue May 02, 2017 7:14 pm UTC**

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

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.

Posted: **Tue May 02, 2017 7:15 pm UTC**

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.

Posted: **Tue May 02, 2017 7:16 pm UTC**

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:

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.

Posted: **Tue May 02, 2017 7:17 pm UTC**

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.

Posted: **Tue May 02, 2017 7:19 pm UTC**

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

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

Posted: **Tue May 02, 2017 7:24 pm UTC**

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

Posted: **Tue May 02, 2017 7:25 pm UTC**

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.

Posted: **Tue May 02, 2017 7:28 pm UTC**

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.

Posted: **Tue May 02, 2017 7:31 pm UTC**

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

Posted: **Tue May 02, 2017 7:33 pm UTC**

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.

Posted: **Tue May 02, 2017 7:33 pm UTC**

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!

Posted: **Tue May 02, 2017 7:34 pm UTC**

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

Posted: **Tue May 02, 2017 7:35 pm UTC**

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

Posted: **Tue May 02, 2017 7:35 pm UTC**

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?

[???]

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?

Posted: **Tue May 02, 2017 7:37 pm UTC**

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.

Posted: **Tue May 02, 2017 7:42 pm UTC**

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.

Posted: **Tue May 02, 2017 7:42 pm UTC**

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?

Posted: **Tue May 02, 2017 7:44 pm UTC**

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?

Posted: **Tue May 02, 2017 7:44 pm UTC**

MathDoofus wrote:WibblyWobbly wrote:MathDoofus wrote:

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?

Posted: **Tue May 02, 2017 7:47 pm UTC**

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.

Posted: **Tue May 02, 2017 7:50 pm UTC**

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.

Posted: **Tue May 02, 2017 7:54 pm UTC**

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

Posted: **Tue May 02, 2017 7:57 pm UTC**

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.

Posted: **Tue May 02, 2017 8:00 pm UTC**

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

Posted: **Tue May 02, 2017 8:04 pm UTC**

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.