Page **1** of **7**

### Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 2:44 pm UTC**

by **MathDoofus**

I fooled around with trying to learn proof by induction a couple of years ago, and I'm just now getting back into it. The original problem that I worked on -- P(n): 1 + 2 + 3 ... + n = n(n + 1)/2 -- is now stumping me.

Let me explain where I'm getting stuck.

The exercise that I'm working from says to first prove the base case.

So here's the base case (using 4).

1 + 2 + 3 + 4 = 4(4 + 1)/2

10 = 4(5)/2

10 = 20/2

10 = 10

So it holds up under the base case.

Next, I need to show that, because the base case is true, that the statement is true for any positive integer, and not just for the example that I used already (4).

Here's how I might do that.

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

I'll regroup and plug (n + 1) into both sides of the equation. [Note that I'm not exactly sure why I have to do that!]

(1 + 2 + 3 + ... n) + (n + 1) = [(n + 1)(n + 1 + 1)]/2

That's where I get stuck. What comes next, and why? And why is it that I simply plugged (n + 1) into the left side (without substituting it for n) but didn't have to do so on the right side? This is all terribly confusing, and it's easy to lose track of the big picture. Any help would be appreciated.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 2:54 pm UTC**

by **doogly**

The reason why you add (n+1) to both sides is because you are proving the general case by doing two things -

- prove the base case

- prove that, provided the n case is true, the n+1 case is true

So that's why you are free to start with the statement of what you're trying to prove in the n case

(1 + ... + n) = n(n+1)/2

and then can add the n+1 to both sides

(1 + ... + n) + (n+1) = n(n+1)/2 + (n+1)

Then you have to finesse that into

(1 + ... + [n+1]) = [n+1]([n+1]+1)/2

You can't just use that line as your (n+1) case though -- that's what you want to prove, that it still works in the n+1 case, so you have to do the finessing algebraicly with only the n case as your starting point.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:13 pm UTC**

by **MathDoofus**

doogly wrote:The reason why you add (n+1) to both sides is because you are proving the general case by doing two things -

- prove the base case

- prove that, provided the n case is true, the n+1 case is true

So that's why you are free to start with the statement of what you're trying to prove in the n case

(1 + ... + n) = n(n+1)/2

and then can add the n+1 to both sides

(1 + ... + n) + (n+1) = n(n+1)/2 + (n+1)

Then you have to finesse that into

(1 + ... + [n+1]) = [n+1]([n+1]+1)/2

You can't just use that line as your (n+1) case though -- that's what you want to prove, that it still works in the n+1 case, so you have to do the finessing algebraicly with only the n case as your starting point.

My user name is the truth, so I'm going to ask a stupid question. Why is it, to test whether (n + 1) is true, I have to add it to both sides? Shouldn't I just add it to the left side?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:17 pm UTC**

by **WibblyWobbly**

So, your statement to be proven is:

1 + 2 + 3 + 4 + ... + n = n*(n+1)/2

The first step, involving the base case, is just to show that your statement is true

for some value of n. In your case, you started with a base case of 4. Showing that the statement is true in this case (where

n = 4 is pretty easy, as you demonstrated.

1 + 2 + 3 + 4 = 10

4 * (4+1) / 2 = 4 * 5 / 2 = 20 / 2 = 10

So, for

n = 4, 1 + 2 + 3 + 4 + ... + n = n*(n+1)/2 is true. Easy enough?

Next step:

Assume your statement (1 + 2 + 3 + 4 + ... + n = n*(n+1)/2) is true for some number n = m. So, we're given that

1 + 2 + 3 + 4 + ... + m = m*(m+1)/2 (substituted

m for

n; call this the "prior equation")

Your goal is to show that the statement 1 + 2 + 3 + 4 + ... + n = n*(n+1)/2 is still true when n = m + 1; that is,1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+1+1)]/2 = [(m+1)(m+2)]/2 (Call this the proof equation)

But what is 1 + 2 + 3 + 4 + ... + m+1? It's 1 + 2 + 3 + 4 + ... + m + (m+1). But we already know what 1 + 2 + 3 + 4 + ... + m is, it comes from the "prior equation", and so we know 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2. So we can substitute [m(m+1)]/2 for 1 + 2 + 3 + 4 + ... + m

So, the proof equation now looks like

[m(m+1)]/2 + (m+1) = [(m+1)(m+2)]/2.

On the left hand side,

(m+1) = 2(m+1)/2 = (2m+2)/2

[m(m+1)]/2 + (2m+2)/2 = [m(m+1) + 2m + 2]/2 = [m^2 + m + 2m + 2]/2 = [m^2 + 3m + 2]/2 = [(m+1)(m+2)]/2.

Gathering everything back up, what this shows is:

Given: 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2 (which is your original statement, 1 + 2 + 3 + 4 + ... + n = [n(n+1)]/2, with

n = m)

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+2)]/2 (which is the same as your original statement, with

n = m+1.

What does that give you? Well, you proved your initial statement is true when n = 4. Now that you've proven that when the statement is true for n = m, it's also true for n = m+1, you know that if the initial statement is true for n = 4, it's also true for n = 5. And you've proven it's true for n = 4, so it's

got to be true for n = 5. But, if it's true for n = 5, it's also got to be true for n = 5+1 = 6. But, if it's true for n = 6, it's also got to be true for n = 6+1 = 7. But, if it's true for n = 7 ... and so on for any positive integer n >= 4. However, since your base case was n = 4, we can't actually say anything concrete about n = 1, 2 or 3 just yet. You can prove those easily enough, though.

What you're doing in the second part is

not showing that if it's true for the base case, it's true for any positive integer. You're skipping steps a little. What you're showing is that if it's true

in some specific case (n = m, where m is some positive integer), we can show it's true for another case (n = m+1; m+1 just happens to be the next greater positive integer). Then you get a chain of statements like "if it's true for this number, it's got to be true for this other number, and if it's true for this other number, it's got to be true for this third number" and so on. That's how you get "it's true for all positive integers".

MathDoofus wrote:doogly wrote:The reason why you add (n+1) to both sides is because you are proving the general case by doing two things -

- prove the base case

- prove that, provided the n case is true, the n+1 case is true

So that's why you are free to start with the statement of what you're trying to prove in the n case

(1 + ... + n) = n(n+1)/2

and then can add the n+1 to both sides

(1 + ... + n) + (n+1) = n(n+1)/2 + (n+1)

Then you have to finesse that into

(1 + ... + [n+1]) = [n+1]([n+1]+1)/2

You can't just use that line as your (n+1) case though -- that's what you want to prove, that it still works in the n+1 case, so you have to do the finessing algebraicly with only the n case as your starting point.

My user name is the truth, so I'm going to ask a stupid question. Why is it, to test whether (n + 1) is true, I have to add it to both sides? Shouldn't I just add it to the left side?

This is a basic fact about equalities: when you add something to the left hand side of an equality, you have to add it to the right side as well, or it's not an equality anymore.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:37 pm UTC**

by **MathDoofus**

WibblyWobbly wrote:So, your statement to be proven is:

Your goal is to show that the statement 1 + 2 + 3 + 4 + ... + n = n*(n+1)/2 is still true when n = m + 1; that is,

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+1+1)]/2 = [(m+1)(m+2)]/2 (Call this the proof equation)

But what is 1 + 2 + 3 + 4 + ... + m+1? It's 1 + 2 + 3 + 4 + ... + m + (m+1). But we already know what 1 + 2 + 3 + 4 + ... + m is, it comes from the "prior equation", and so we know 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2. So we can substitute [m(m+1)]/2 for 1 + 2 + 3 + 4 + ... + m

So, the proof equation now looks like

[m(m+1)]/2 + (m+1) = [(m+1)(m+2)]/2.

On the left hand side,

(m+1) = 2(m+1)/2 = (2m+2)/2

[m(m+1)]/2 + (2m+2)/2 = [m(m+1) + 2m + 2]/2 = [m^2 + m + 2m + 2]/2 = [m^2 + 3m + 2]/2 = [(m+1)(m+2)]/2.

Gathering everything back up, what this shows is:

Given: 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2 (which is your original statement, 1 + 2 + 3 + 4 + ... + n = [n(n+1)]/2, with n = m)

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+2)]/2 (which is the same as your original statement, with n = m+1.

Thank you for this explanation. The quoted portions above are those parts that I don't understand.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:45 pm UTC**

by **WibblyWobbly**

What is it that you don't understand? I can be more helpful if I know specifically what is wrong.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:50 pm UTC**

by **MathDoofus**

First, I don't understand how we derive the so-called "proof equation." Second, I don't understand how we can simply plug in the prior equation (isn't this a logical fallacy insofar as we're at least partially assuming what we want to prove?). Third, I don't understand how we can simply set the left side equal to the right after plugging in the prior equation. Finally, I don't understand the algebraic manipulations to arrive at the ultimate conclusion.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 3:57 pm UTC**

by **doogly**

The "proof equation" isn't derived formally here. We hypothesized it, and now we're going to prove it.

We can plug it in because at that point, we are proving "If it's true for n, then it's true for n+1." So we get to assume it's true for n, and then try to prove it for n+1.

We haven't actually proved it for n though, and if we stopped here, we would have a fallacious proof. We have to also prove a base case, say for n=1. Once we do that, knowing that n implies n+1 means that proving it for case 1 proves it for case 2, 3, 4, 5, .... all natural numbers.

For your third point, I'm not sure this is a third point. Our prior equation was

(1 + n) = n(n+1)/2

then we just add the same term to both sides. It could be literally anything and that's fine.

(1 + n) + caterpillars = n(n+1)/2 + caterpillars

This is totally legit. We don't actually care about caterpillars, we care about n+1 because we really want the left side to look like

(1 + .... n + 1)

because that is what we care about, and adding on that last term is how we get it to look like that.

For your fourth point, that will require some sweat and pencil equity, but if you understand why we're trying to do the things we're doing then there's hope for chugging through, but it will be very difficult indeed from the perspective of aimless manipulations, so let's make sure you're clear on the first three points, aight?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 4:15 pm UTC**

by **WibblyWobbly**

doogly wrote:The "proof equation" isn't derived formally here. We hypothesized it, and now we're going to prove it.

We can plug it in because at that point, we are proving "If it's true for n, then it's true for n+1." So we get to assume it's true for n, and then try to prove it for n+1.

We haven't actually proved it for n though, and if we stopped here, we would have a fallacious proof. We have to also prove a base case, say for n=1. Once we do that, knowing that n implies n+1 means that proving it for case 1 proves it for case 2, 3, 4, 5, .... all natural numbers.

This is key. If our statement to prove with induction is P(n), we need to first set up the fact that P(n) is true

somewhere. This is why proving the base case is often considered the first step. Then, the induction step is:

Given P(n) is true for some n (in our case, n = m), prove that P(n) is true for some related value (in our case, n = m+1).

If we couldn't prove P(n) is true for some value, somewhere, the whole thing falls apart like you (MathDoofus) suggested. But since we showed P(n) is true in the base case, it's true

somewhere, and the idea of the induction step is to show that "If it's true somewhere, we can show it's true somewhere else".

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 4:15 pm UTC**

by **MathDoofus**

I don't understand how the proof equation was derived, hypothesized, or what have you. At that point, from what I can see, we know only one thing, which is that the original equation works for some base case. I don't understand how can we just substitute what we're trying to prove into something and arrive at a proof from that substitution.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 4:16 pm UTC**

by **MathDoofus**

WibblyWobbly wrote:

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+1+1)]/2 = [(m+1)(m+2)]/2 (Call this the proof equation)

But what is 1 + 2 + 3 + 4 + ... + m+1? It's 1 + 2 + 3 + 4 + ... + m + (m+1). But we already know what 1 + 2 + 3 + 4 + ... + m is, it comes from the "prior equation", and so we know 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2. So we can substitute [m(m+1)]/2 for 1 + 2 + 3 + 4 + ... + m

So, the proof equation now looks like

[m(m+1)]/2 + (m+1) = [(m+1)(m+2)]/2.

On the left hand side,

(m+1) = 2(m+1)/2 = (2m+2)/2

[m(m+1)]/2 + (2m+2)/2 = [m(m+1) + 2m + 2]/2 = [m^2 + m + 2m + 2]/2 = [m^2 + 3m + 2]/2 = [(m+1)(m+2)]/2.

Also, is there an error in the proof equation? On the right side, how did we get an (m + 2)?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 4:20 pm UTC**

by **WibblyWobbly**

MathDoofus wrote:WibblyWobbly wrote:

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+1+1)]/2 = [(m+1)(m+2)]/2 (Call this the proof equation)

But what is 1 + 2 + 3 + 4 + ... + m+1? It's 1 + 2 + 3 + 4 + ... + m + (m+1). But we already know what 1 + 2 + 3 + 4 + ... + m is, it comes from the "prior equation", and so we know 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2. So we can substitute [m(m+1)]/2 for 1 + 2 + 3 + 4 + ... + m

So, the proof equation now looks like

[m(m+1)]/2 + (m+1) = [(m+1)(m+2)]/2.

On the left hand side,

(m+1) = 2(m+1)/2 = (2m+2)/2

[m(m+1)]/2 + (2m+2)/2 = [m(m+1) + 2m + 2]/2 = [m^2 + m + 2m + 2]/2 = [m^2 + 3m + 2]/2 = [(m+1)(m+2)]/2.

Also, is there an error in the proof equation? On the right side, how did we get an (m + 2)?

It's [(m+1) + 1]. Our original equation was 1 + 2 + 3 + ... + n = [n(n+1)]/2. If you substitute m+1 for n, you get 1 + 2 + 3 + ... + m+1 = [(m+1)((m+1)+1)]/2 = [(m+1)(m+2)]/2

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 4:38 pm UTC**

by **MathDoofus**

WibblyWobbly wrote:MathDoofus wrote:WibblyWobbly wrote:

1 + 2 + 3 + 4 + ... + (m+1) = [(m+1)(m+1+1)]/2 = [(m+1)(m+2)]/2 (Call this the proof equation)

But what is 1 + 2 + 3 + 4 + ... + m+1? It's 1 + 2 + 3 + 4 + ... + m + (m+1). But we already know what 1 + 2 + 3 + 4 + ... + m is, it comes from the "prior equation", and so we know 1 + 2 + 3 + 4 + ... + m = [m(m+1)]/2. So we can substitute [m(m+1)]/2 for 1 + 2 + 3 + 4 + ... + m

So, the proof equation now looks like

[m(m+1)]/2 + (m+1) = [(m+1)(m+2)]/2.

On the left hand side,

(m+1) = 2(m+1)/2 = (2m+2)/2

[m(m+1)]/2 + (2m+2)/2 = [m(m+1) + 2m + 2]/2 = [m^2 + m + 2m + 2]/2 = [m^2 + 3m + 2]/2 = [(m+1)(m+2)]/2.

Also, is there an error in the proof equation? On the right side, how did we get an (m + 2)?

It's [(m+1) + 1]. Our original equation was 1 + 2 + 3 + ... + n = [n(n+1)]/2. If you substitute m+1 for n, you get 1 + 2 + 3 + ... + m+1 = [(m+1)((m+1)+1)]/2 = [(m+1)(m+2)]/2

I am going to work back through this with pen and paper to see if I can get there. Assuming that I can (that's a huge assumption because I'm essentially suffering from a math-related learning disability), my next question is "how's it permissible to mix the proof equation and the prior equation?"

Some progress; see belowWhen I want to prove that the (n + 1) case is true (where I've already proved that the whole thing holds for some n; in this case, I used 4), I add (n + 1) to both sides, as below:

[Started with] 1 + 2 + 3 + ... + n = n(n + 1)/2

[Add (n + 1) to both sides] 1 + 2 +3 + ... + n + (n + 1) = [n(n + 1)/2] + (n + 1)

[Recognize that, using the starting equation, I can substitute part of the right side for part of the left side] n(n + 1)/2 + (n + 1) = [n(n + 1)/2] + (n + 1)

And that's where I'm currently stuck!

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:12 pm UTC**

by **Qaanol**

Are you having a conceptual problem with the idea of induction, or a mechanical problem with applying induction to this particular problem?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:16 pm UTC**

by **MathDoofus**

Qaanol wrote:Are you having a conceptual problem with the idea of induction, or a mechanical problem with applying induction to this particular problem?

The concept, in general terms, I think that I've got down. All that we need to be able to perform induction is a base case and something that depends on the countability of integers. (Not to say that I'd get the inductive step in any particular problem; that's really freaking hard because each problem is like starting over).

I'm now having trouble applying induction to this particular problem; I've noted above where I'm stuck (trying to work through everything using pen and paper).

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:25 pm UTC**

by **WibblyWobbly**

MathDoofus wrote:Some progress; see below

When I want to prove that the (n + 1) case is true (where I've already proved that the whole thing holds for some n; in this case, I used 4), I add (n + 1) to both sides, as below:

[Started with] 1 + 2 + 3 + ... + n = n(n + 1)/2

[Add (n + 1) to both sides] 1 + 2 +3 + ... + n + (n + 1) = [n(n + 1)/2] + (n + 1)

[Recognize that, using the starting equation, I can substitute part of the right side for part of the left side] n(n + 1)/2 + (n + 1) = [n(n + 1)/2] + (n + 1)

And that's where I'm currently stuck!

Good progress. On this line,

MathDoofus wrote:[Add (n + 1) to both sides] 1 + 2 +3 + ... + n + (n + 1) = [n(n + 1)/2] + (n + 1)

The statement you're ultimately trying to prove is "The sum of the first n positive integers, P(n), is given by [n(n+1)]/2". What you want to recognize is that the left-hand side of the quoted portion above ("1 + 2 + 3 + ... + n + (n+1)") is the sum of the first (n+1) positive integers, i.e., it's P(n+1). What you want to do now is algebraically manipulate the right-hand side of that equation to show that "[n(n+1)/2] + (n+1)" is equal to [(n+1)((n+1)+1]/2.

Because that proves P(n+1) is just P(n), that is "[n(n+1)]/2", with n replaced by (n+1). Then, with the fact that P(n) is true in the base case, proves P(n) is true for all subsequent cases.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:30 pm UTC**

by **MathDoofus**

WibblyWobbly wrote:The statement you're ultimately trying to prove is "The sum of the first n positive integers, P(n), is given by [n(n+1)]/2". What you want to recognize is that the left-hand side of the quoted portion above ("1 + 2 + 3 + ... + n + (n+1)") is the sum of the first (n+1) positive integers, i.e., it's P(n+1). What you want to do now is algebraically manipulate the right-hand side of that equation to show that "[n(n+1)/2] + (n+1)" is equal to [(n+1)((n+1)+1]/2.

Because that proves P(n+1) is just P(n), that is "[n(n+1)]/2", with n replaced by (n+1). Then, with the fact that P(n) is true in the base case, proves P(n) is true for all subsequent cases.

I'm not exactly certain why the proof works (it does feel like I'm assuming the conclusion, at least in part, which is question-begging), but I am having trouble with the algebra at this point. How do I avoid having an n-squared somewhere?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:34 pm UTC**

by **WibblyWobbly**

MathDoofus wrote:WibblyWobbly wrote:The statement you're ultimately trying to prove is "The sum of the first n positive integers, P(n), is given by [n(n+1)]/2". What you want to recognize is that the left-hand side of the quoted portion above ("1 + 2 + 3 + ... + n + (n+1)") is the sum of the first (n+1) positive integers, i.e., it's P(n+1). What you want to do now is algebraically manipulate the right-hand side of that equation to show that "[n(n+1)/2] + (n+1)" is equal to [(n+1)((n+1)+1]/2.

Because that proves P(n+1) is just P(n), that is "[n(n+1)]/2", with n replaced by (n+1). Then, with the fact that P(n) is true in the base case, proves P(n) is true for all subsequent cases.

I'm not exactly certain why the proof works (it does feel like I'm assuming the conclusion, at least in part, which is question-begging), but I am having trouble with the algebra at this point. How do I avoid having an n-squared somewhere?

An n-squared term is probably going to pop up no matter what. What you might want to do is go ahead and run with it (expand out the polynomial and collect all the terms), and then factor it at the end.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:46 pm UTC**

by **Qaanol**

MathDoofus wrote:I'm not exactly certain why the proof works (it does feel like I'm assuming the conclusion, at least in part, which is question-begging)

It sounds like you are having trouble with the concept of mathematical induction.

MathDoofus wrote:The concept, in general terms, I think that I've got down. All that we need to be able to perform induction is a base case and something that depends on the countability of integers.

Understanding “in general terms” isn’t good enough. If you really think you’ve “got it down”, could you please explain, to the best of your ability, *why* mathematical induction works?

Otherwise, please acknowledge that it is the concept you need help with, not the mechanics of this one particular problem.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:50 pm UTC**

by **MathDoofus**

Qaanol wrote:MathDoofus wrote:I'm not exactly certain why the proof works (it does feel like I'm assuming the conclusion, at least in part, which is question-begging)

It sounds like you are having trouble with the concept of mathematical induction.

MathDoofus wrote:The concept, in general terms, I think that I've got down. All that we need to be able to perform induction is a base case and something that depends on the countability of integers.

Understanding “in general terms” isn’t good enough. If you really think you’ve “got it down”, could you please explain, to the best of your ability, *why* mathematical induction works?

Otherwise, please acknowledge that it is the concept you need help with, not the mechanics of this one particular problem.

As far as I can tell, mathematical induction is a valid method of proof for those things that depend on countability. So, if the thing that we're looking proceeds step-wise in a regular way (e.g., counting by one, counting by two, or some other meaningful way of determining how to arrive at the next higher value), then we can use mathematical induction to show that it's true for every possible value of n.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:50 pm UTC**

by **Qaanol**

MathDoofus wrote:As far as I can tell, mathematical induction is a valid method of proof for those things that depend on countability.

*Why* is it valid?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:52 pm UTC**

by **Zohar**

You've described when someone might turn to induction. Can you explain why this is a valid method of proof? So I checked a base case, I assumed something and checked for n+1. Why does this mean what I checked is true for any number? How is this a proof?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:55 pm UTC**

by **MathDoofus**

Qaanol wrote:MathDoofus wrote:As far as I can tell, mathematical induction is a valid method of proof for those things that depend on countability.

*Why* is it valid?

Because one of the foundational assumptions when something is countable is that, if that thing holds for one member of that countable series, then it should also hold for the next step, and for the step after that, etc.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:56 pm UTC**

by **Zohar**

No, that's not the correct explanation. The natural numbers (1, 2, 3, 4,...) are a countable series. It's true that 2 is divisible by two, but the next member in the series, 3, is not divisible by two.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 6:59 pm UTC**

by **MathDoofus**

Zohar wrote:No, that's not the correct explanation. The natural numbers (1, 2, 3, 4,...) are a countable series. It's true that 2 is divisible by two, but the next member in the series, 3, is not divisible by two.

That strikes me as a trivial example. Why don't you tell me what you're after? As a beginner, I'm not going to be able to create novel examples of things that are provable via mathematical induction.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 7:07 pm UTC**

by **Qaanol**

MathDoofus wrote:Why don't you tell me what you're after? As a beginner, I'm not going to be able to create novel examples of things that are provable via mathematical induction.

We are not asking for examples. We are asking you to explain, as best you understand it, why mathematical induction works.

(Hint: the correct answer for you is almost certainly “I do not understand why mathematical induction works.”)

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 7:13 pm UTC**

by **MathDoofus**

Qaanol wrote:MathDoofus wrote:Why don't you tell me what you're after? As a beginner, I'm not going to be able to create novel examples of things that are provable via mathematical induction.

We are not asking for examples. We are asking you to explain, as best you understand it, why mathematical induction works.

(Hint: the correct answer for you is almost certainly “I do not understand why mathematical induction works.”)

Because, assuming that the example chosen is a one that fits the application of mathematical induction, the (what seem to me as a beginner to be valid) principles that (1) integers can be placed into an order and (2) you can always get to the next biggest integer from the lower one make mathematical induction a valid method of proof. There may be examples of induction involving non-countable things but those are way, way over my head.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 7:20 pm UTC**

by **Qaanol**

You keep repeating premises (integers are countable) and conclusions (induction works) without providing any line of reasoning to connect the two. You are completely skipping over the “why”, which is what I asked you to explain.

Is there a reason you are so reluctant to acknowledge that you do not understand why induction works?

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 7:22 pm UTC**

by **MathDoofus**

Qaanol wrote:You keep repeating premises (integers are countable) and conclusions (induction works) without providing any line of reasoning to connect the two. You are completely skipping over the “why”, which is what I asked you to explain.

Is there a reason you are so reluctant to acknowledge that you do not understand why induction works?

Please reveal the secret. It should be clear to everyone that I'm struggling, and I see no point in dwelling on my ignorance other than for posters to prove some rhetorical point. I have a vague sense that the combination of a base case (n) and countability (i.e., that integers can be put into order) means that (in appropriate cases) the (n + 1) case will be true no matter what (n) case is chosen.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 7:46 pm UTC**

by **Qaanol**

MathDoofus wrote:Please reveal the secret. It should be clear to everyone that I'm struggling, and I see no point in dwelling on my ignorance other than for posters to prove some rhetorical point. I have a vague sense that the combination of a base case (n) and countability (i.e., that integers can be put into order) means that (in appropriate cases) the (n + 1) case will be true no matter what (n) case is chosen.

Yes, it is quite clear that you are struggling with the concept of induction. Yet when I asked point-blank whether you needed help with the concept of induction, or with its application to one particular problem, you claimed that you got the concept and just needed help applying it to a problem.

The point is not to “dwell on your ignorance” but for you to be clear about what it is you want help with. I rather suspect that as soon as you understand what induction is and why it works, that you will be able to see for yourself how to apply it to the problem you are working on.

Moreover, attempting to deceive other people about your own abilities is not going to get you the help you need, because you claimed to already know the thing that you actually still need to learn.

When you are ready to acknowledge that you would like help understanding how and why induction works, there are many people here who would be happy to help you. You just have to be honest about what you do and do not know. It is perfectly fine to not know things—that’s a prerequisite for learning after all!

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 8:27 pm UTC**

by **Meteoric**

In computer science, "induction" is called "recursion".

Suppose I have a big problem. I don't know how to solve it. But I figure out a trick - if I could solve a smaller problem, then I could use that to solve my big problem.

Now that smaller problem is still too big to solve. But I apply my trick again, and solve it in terms of a yet smaller problem.

I keep doing this, until the problem becomes small enough that I can solve it outright. And now I can solve everything back up the chain - including the original, large problem.

That's induction. There's two things going on: I have the base step, a problem small enough that I can solve it outright. And I have the induction step, a trick for turning a big problem into a smaller problem. Using these two parts together, I can solve a problem of any size - by reducing it until it gets down to the base step.

Now in math, we usually write it the other way around, and think of induction as going up from the base step, instead of going down from the original big step. But these are doing the same thing. The hard part is almost always in figuring out how to make the trick work - how to take a big problem and reduce it to a smaller problem. If you had a black-box solution for n=999, how could you use it to solve n=1000? Usually, the answer is "do a bunch of algebra on the solution to n=999 until it looks like a solution for n=1000".

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 9:24 pm UTC**

by **MathDoofus**

Qaanol wrote:When you are ready to acknowledge that you would like help understanding how and why induction works, there are many people here who would be happy to help you. You just have to be honest about what you do and do not know. It is perfectly fine to not know things—that’s a prerequisite for learning after all!

I will admit my ignorance. There's something about induction that feels like I'm improperly assuming the truth of what I hope to prove.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 9:26 pm UTC**

by **MathDoofus**

Qaanol wrote:

When you are ready to acknowledge that you would like help understanding how and why induction works, there are many people here who would be happy to help you. You just have to be honest about what you do and do not know. It is perfectly fine to not know things—that’s a prerequisite for learning after all!

I am also struggling with the algebra of the final step; I don't know how to get rid of the n-squareds on both sides of the equation.

### Re: Mathematical Induction - Introductory Question

Posted: **Mon May 01, 2017 11:36 pm UTC**

by **Qaanol**

MathDoofus wrote:I will admit my ignorance. There's something about induction that feels like I'm improperly assuming the truth of what I hope to prove.

Great!

That is a common feeling for people just learning about induction. One analogy that sometimes helps is to think about climbing a ladder.

1. The base case is to show that you can get onto the bottom rung of the ladder.

2. The induction step is to show that *if* you are on rung n of the ladder, *then* you can climb up to rung (n+1).

Together, those two things let you climb all the way up the ladder. Do you see how? Step 1 gets you onto *some* rung of the ladder, and step 2 says that from *any* rung you can get to the *next* rung. You’ll never reach a rung where you get stuck, because step 2 shows that you can climb one rung higher.

• • •

Another way to look at it, is to think about counterexamples. You are trying to prove that some statement is true for *every* positive integer.

If the statement is *not* true for every positive integer, then there is at least one counterexample. Let c be the *smallest* counterexample, so the statement you’re dealing with is true for all positive integers less than c, but false for c.

Look at (c-1), which is either 0 (if c=1) or else it is a positive integer. If you can prove directly that the statement is true for n=1, then c must be greater than 1, so (c-1) must be a positive integer.

Thus you know the statement is true for (c-1) since it is smaller than c. And suppose that you can prove “Whenever the statement is true for a positive integer n, then it is also true for (n+1)”, which is just the induction step.

Now, since the statement you care about is true for (c-1), and whenever it is true for some positive integer it is also true for the next one, that tells you the statement is true for c. So c is not actually a counterexample at all.

Recall that c was supposed to be the *smallest* counterexample. Hence any number we think might be the smallest counterexample, is not actually a counterexample. So there cannot be a smallest counterexample, and thus there are no counterexamples at all.

We have just shown that if a statement is true for n=1, *and* whenever the statement is true for a positive integer n it is also true for (n+1), then there cannot be any positive integers where the statement is false. There cannot be a smallest counterexample, so there cannot be any counterexamples. The statement must be true for all positive integers.

• • •

The tricky part is recognizing that the induction step is *not* circular reasoning. It requires you to prove that *if* the statement is true for n, *then* the statement is true for (n+1). The induction step is where you demonstrate that it is possible to get from *any* arbitrary rung of the ladder up to the next rung.

For the problem you are working on, the sum of the first n positive integers, the induction step is as follows:

Suppose that (1+2+3+…+k) = k(k+1)/2 for *some* positive integer k. So you are standing on rung k.

You have to *prove* that you can get to rung (k+1), assuming that you have already gotten to rung k.

What would it mean to stand on rung (k+1)? Well, it would mean that (1+2+3+…+k+(k+1)) = (k+1)((k+1)+1)/2. In other words, the statement you are working with would have to be true for n=(k+1).

Now how can we prove that? Well, remember that we only have to show that we can climb *one* rung at a time. So *assuming* we have already reached rung k, that means we know (1+2+3+…+k) = k(k+1)/2.

Since we know that about k, we can just plug it in:

(1+2+3+…+k+(k+1)) = (1+2+3+…+k) + (k+1)

= k(k+1)/2 + (k+1) because we know what (1+2+3+…+k) equals, because we are already standing on rung k.

Now, that is not exactly what you are trying to show. You need to do some algebra. You need to show that k(k+1)/2 + (k+1) is actually the same as (k+1)((k+1)+1)/2. You have to show that you really can reach rung (k+1).

And once you do that, you will have shown that *if* (1+2+3+…+k) = k(k+1)/2, *then* (1+2+3+…+k+(k+1)) = (k+1)((k+1)+1)/2. In other words, you will have shown that *if* you are already on rung k, *then* you can step up to rung (k+1).

And once you have done so, that means if you start *anywhere* on the ladder, you can climb up as high as you want, because you can just keep stepping up one rung at a time. All that remains is to show that you can get onto the ladder at all, which is just the base case. Pick some positive integer b (usually b=1 is a good choice) and show that the statement is true for n=b. In other words, show that you can get onto rung b of the ladder.

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:07 am UTC**

by **Sizik**

An important thing to mention is that induction doesn't help you derive the "1+2+...+n = n(n+1)/2" equation, it only proves that it's true.

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:20 am UTC**

by **MathDoofus**

Qaanol wrote:

Another way to look at it, is to think about counterexamples. You are trying to prove that some statement is true for *every* positive integer.

If the statement is *not* true for every positive integer, then there is at least one counterexample. Let c be the *smallest* counterexample, so the statement you’re dealing with is true for all positive integers less than c, but false for c.

Look at (c-1), which is either 0 (if c=1) or else it is a positive integer. If you can prove directly that the statement is true for n=1, then c must be greater than 1, so (c-1) must be a positive integer.

Thus you know the statement is true for (c-1) since it is smaller than c. And suppose that you can prove “Whenever the statement is true for a positive integer n, then it is also true for (n+1)”, which is just the induction step.

Now, since the statement you care about is true for (c-1), and whenever it is true for some positive integer it is also true for the next one, that tells you the statement is true for c. So c is not actually a counterexample at all.

Recall that c was supposed to be the *smallest* counterexample. Hence any number we think might be the smallest counterexample, is not actually a counterexample. So there cannot be a smallest counterexample, and thus there are no counterexamples at all.

We have just shown that if a statement is true for n=1, *and* whenever the statement is true for a positive integer n it is also true for (n+1), then there cannot be any positive integers where the statement is false. There cannot be a smallest counterexample, so there cannot be any counterexamples. The statement must be true for all positive integers.

Your reply is thorough and thoughtful - thank you! I'm quoting only the first portion because that's where my confusion begins. I don't understand what you mean about the "smallest counterexample" stuff. Is that an admonition to use zero or 1 as the base case every time?

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:22 am UTC**

by **MathDoofus**

Qaanol wrote:The tricky part is recognizing that the induction step is *not* circular reasoning. It requires you to prove that *if* the statement is true for n, *then* the statement is true for (n+1). The induction step is where you demonstrate that it is possible to get from *any* arbitrary rung of the ladder up to the next rung.

For the problem you are working on, the sum of the first n positive integers, the induction step is as follows:

Suppose that (1+2+3+…+k) = k(k+1)/2 for *some* positive integer k. So you are standing on rung k.

You have to *prove* that you can get to rung (k+1), assuming that you have already gotten to rung k.

What would it mean to stand on rung (k+1)? Well, it would mean that (1+2+3+…+k+(k+1)) = (k+1)((k+1)+1)/2. In other words, the statement you are working with would have to be true for n=(k+1).

Now how can we prove that? Well, remember that we only have to show that we can climb *one* rung at a time. So *assuming* we have already reached rung k, that means we know (1+2+3+…+k) = k(k+1)/2.

Since we know that about k, we can just plug it in:

(1+2+3+…+k+(k+1)) = (1+2+3+…+k) + (k+1)

= k(k+1)/2 + (k+1) because we know what (1+2+3+…+k) equals, because we are already standing on rung k.

Now, that is not exactly what you are trying to show. You need to do some algebra. You need to show that k(k+1)/2 + (k+1) is actually the same as (k+1)((k+1)+1)/2. You have to show that you really can reach rung (k+1).

And once you do that, you will have shown that *if* (1+2+3+…+k) = k(k+1)/2, *then* (1+2+3+…+k+(k+1)) = (k+1)((k+1)+1)/2. In other words, you will have shown that *if* you are already on rung k, *then* you can step up to rung (k+1).

And once you have done so, that means if you start *anywhere* on the ladder, you can climb up as high as you want, because you can just keep stepping up one rung at a time. All that remains is to show that you can get onto the ladder at all, which is just the base case. Pick some positive integer b (usually b=1 is a good choice) and show that the statement is true for n=b. In other words, show that you can get onto rung b of the ladder.

The second part where I'm extremely confused is how it's permissible to use a base case (as k), and then plug in the (k + 1) case on both sides. That seems circular to me. Can you explain this further?

EditTo put my second area of confusion in different words, the inductive stuff itself feels like I'm setting k and (k + 1) equal to k and (k + 1), and that's what feels unsatisfactory.

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:26 am UTC**

by **Meteoric**

I've been doing calculations all day, and I found out - at long last - that the sum of the numbers from 1 through 100 is 5,050.

Now that you know that, can you tell me the sum of the numbers from 1 through 101? Isn't it just 5,050+101?

That's what we're doing in the induction step. We're saying - hey, we know the sum of 1 through k. The sum of 1 through (k+1) is just that amount, plus the next number.

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:30 am UTC**

by **MathDoofus**

Meteoric wrote:I've been doing calculations all day, and I found out - at long last - that the sum of the numbers from 1 through 100 is 5,050.

Now that you know that, can you tell me the sum of the numbers from 1 through 101? Isn't it just 5,050+101?

That's what we're doing in the induction step. We're saying - hey, we know the sum of 1 through k. The sum of 1 through (k+1) is just that amount, plus the next number.

I don't see where we get the sum of "1 through k." We have the sum from a base case, but the stuff involving k and (k + 1) seems circular to me, for the reasons described above.

### Re: Mathematical Induction - Introductory Question

Posted: **Tue May 02, 2017 12:34 am UTC**

by **Meteoric**

You get it because I was working on it and told you, of course. The question is, how did I get it? And really, I'll admit it: I know the answer because another guy calculated the sum of 1 through 99, and he told me. That guy talked to another guy who calculated the sum of 1 through 98, and so on down the line, until you get to somebody who had a problem that they could solve by themselves.

The process is recursive, but not circular. It's not looping back on itself - the 101st sum doesn't depend on already knowing the 101st sum. It only depends on the previous result, the 100th sum. You may have to recurse through the process a bunch of times - but it's always a finite bunch of times that bottoms out somewhere, never a loop.