Mathematical Induction - Introductory Question

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 12:37 am UTC

Meteoric wrote:If you can, then the induction proves the proposition P(n) for every n, since:

P(1) is the base case

P(2) holds, by taking a step up from P(1)

P(3) holds, by taking a step up from P(2)

and so on.

That's what the induction step is about: we're saying, can we find a generalized way to get from P(k) to P(k+1)? If so, we can use it to get everywhere, because starting at 1 and adding one at a time lets you get to any natural number.

There's nothing circular happening here. There is definitely a recursive process, but it doesn't loop back on itself - it just descends down and down. The 101st sum depends on the 100th sum, which depends on the 99th sum, which depends on the 98th sum, which depends on etc down to the first sum.


But what about the fact that k and (k + 1) end up on both sides of an equation - that's what I don't understand. That seems circular because I'm just doing algebraic operations (poorly!) with stuff that I've assumed, and not with anything that I've proved (other than a trivial example involving the base case).

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 12:48 am UTC

You're correct that this step DOES NOT prove that the assumption is actually true. It is not supposed to prove that. It is just proving that IF the assumption is true, THEN the conclusion is also true. Do you see why the induction step proves this if-then statement?
No, even in theory, you cannot build a rocket more massive than the visible universe.

User avatar
Eebster the Great
Posts: 2929
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Mathematical Induction - Introductory Question

Postby Eebster the Great » Tue May 02, 2017 12:49 am UTC

Another way of looking at it is by repeated application of the logical form known as modus ponens. This form goes like this:

1. If A then B
2. A
3. Therefore B

As an example:

1. If a number is even, then it is divisible by 2.
2. The number 6 is even.
3. Therefore the number 6 is divisible by 2.

This form of proof is called "valid" because the conclusion follows from the premises. Obviously your premises still need to be true to have a sound argument. For instance, the same valid form is used in the following argument:

1. If a number is even, then it is divisible by 2.
2. The number 5 is even.
3. Therefore the number 5 is divisible by 2.

Obviously this argument is unsound because the second premise is false. So we have to first prove our premises are true in order for this type of argument to prove the conclusion is true.


In the case of mathematical induction, you are basically applying modus ponens over and over. In your example, you start with the base case:

The sum of the first four numbers is 4 · (4+1) / 2.

I won't repeat the proof of this claim because it is obvious and you have already done it, but the point is that it does need to be proven. Next we prove the inductive step.

If the sum of the first four numbers is 4 · (4+1) / 2, then the sum of the first five numbers is 5 · (5+1) / 2.

In practice, you wouldn't prove this in real life, because again, it is already obvious. But I am demonstrating this form for a reason. Having proven both of these premises, you can now apply modus ponens to prove the conclusion:

Therefore the sum of the first five numbers is 5 · (5+1) / 2.

Putting them all in the same order as above:

1. If the sum of the first four numbers is 4 · (4+1) / 2, then the sum of the first five numbers is 5 · (5+1) / 2.
2. The sum of the first four numbers is 4 · (4+1) / 2.
3. Therefore the sum of the first five numbers is 5 · (5+1) / 2.

But this isn't all that useful. After all, we want to know that this works for all integers greater than 4, not just for 5. We could, if we knew how, prove the following claim too:

If the sum of the first five numbers is 5 · (5+1) / 2, then the sum of the first six numbers is 6 · (6+1) / 2.

Then we could apply modus ponens again:

1. If the sum of the first five numbers is 5 · (5+1) / 2, then the sum of the first six numbers is 6 · (6+1) / 2.
2. The sum of the first five numbers is 5 · (5+1) / 2. (This is the conclusion we reached previously. We've proved it, so we know it's true.)
3. Therefore the sum of the first six numbers is 6 · (6+1) / 2.

Obviously this is going to take forever to prove for all numbers. Instead, we need to prove it for a general case. If we can show that our premise 1 isn't just true for n = 4 or n = 5, but for all n, then we will be able to repeat this process as many times as we like without having to prove a new thing each time. This is the inductive step. We are proving the general premise:

If the sum of the first n numbers is n(n+1) / 2, then the sum of the first n+1 numbers is (n+1)((n+1)+1) / 2.

Having proven this, we can prove every "Premise 2" above simply by letting n equal that particular number. To prove every "Premise 1," first we prove the base case, then we apply modus ponens to prove the next one up, then repeat that as many times as we need.


Now clearly, this will only work if every integer can be reached by starting at the base case and moving up one step at a time. This property is not precisely countability but actually well-ordering. We say that the natural numbers are "well-ordered" under the relation of '<' because every subset has a least element. More formally, we say that for every subset S of N, there exists some element a such that there does not exist any element b in the subset with b < a. In your example, you are considering the subset of all integers greater than or equal to 4. In this subset, there is no element b such that b < 4. This turns out to be sufficient to prove that mathematical induction will work. An example of a set that is countable but not well-founded is the integers. We can never prove some claim about all integers with just one mathematical induction argument. Instead, you can just prove it for all integers greater than some least element. (However, we could first prove it true for all integers greater than some base case, then separately prove it true for all integers less than that base case, and thus prove it for all integers.)

In addition to showing there is some least element, we also have to show that every other element can be "reached" by starting at the least element. In this case, we are increasing by 1 every step. So we have to know that every natural number is either one more than some other natural number or is the least element. This is usually taken as an axiom or part of the definition of the natural numbers. And yes, this is something that does rely on countability, but it is actually a stronger condition than countability.

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 12:51 am UTC

Meteoric wrote:You're correct that this step DOES NOT prove that the assumption is actually true. It is not supposed to prove that. It is just proving that IF the assumption is true, THEN the conclusion is also true. Do you see why the induction step proves this if-then statement?


No, I do not see that. Here's why:

I've proved the base case (with a trivial example). But that gets me the "rung" using the ladder metaphor.

I then generalize to any number (k) and its plus-one (k + 1). But I'm not proving anything about (k), so I don't see how I can prove (k + 1). Does that make sense?

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 1:05 am UTC

It sounds to me like you are confused about proving conditionals in general. To prove that A implies B, your proof will go like this:
Assume A. Then [some reasoning goes here]. Therefore B.

If you like, you can replace the words "assume A" with "suppose A", or "consider the situation where A is true", or "let's see what would happen if A were true". These all mean the same thing.
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

Postby MathDoofus » Tue May 02, 2017 1:11 am UTC

Meteoric wrote:It sounds to me like you are confused about proving conditionals in general. To prove that A implies B, your proof will go like this:
Assume A. Then [some reasoning goes here]. Therefore B.

If you like, you can replace the words "assume A" with "suppose A", or "consider the situation where A is true", or "let's see what would happen if A were true". These all mean the same thing.


But how does "assume A, therefore B" prove anything? Here's where I'm confused:

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

Here's where I mash up k and (k + 1), for some reason, which strikes me as assuming both k and (k + 1).

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

Here's another part that feels like cheating, where I substitute the right side of the first equation for part of the left side of a later one.

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

Below is where I get stuck on the algebra and how to "solve" this equation.

(k^2 + k)/2 + (k + 1) = (k^2 + k)/2 + (k + 1)

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 1:18 am UTC

MathDoofus wrote:But how does "assume A, therefore B" prove anything?

That's how the proof of a conditional works. Work directly with some non-induction examples, and I think you will see why this is the obviously correct way to prove conditionals. It doesn't prove that A is true, nor that B is true. But it does prove that if A is true, then B is true.
Here's where I'm confused:

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

This is your premise. You get to assume this.
Here's where I mash up k and (k + 1), for some reason, which strikes me as assuming both k and (k + 1).

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

This isn't an assumption. The line above was an assumption, but given that assumption, this is a totally valid step: you're adding (k+1) to both sides.

Here's another part that feels like cheating, where I substitute the right side of the first equation for part of the left side of a later one.

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

I don't think this is what you want to do. You want to end up with an equation that says "the sum of 1 through (k+1) is this nice expression". If you do this step, you no longer have the part about the sum of 1 through (k+1).

Instead, you take your left-hand side, and you leave it completely alone. 1+2+3+...+k+(k+1) is exactly what you want over there.

On your right-hand side, you do some algebra to show that k(k+1)/2 + (k+1) is actually the same thing as (k+1)(k+2)/2.
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

Postby MathDoofus » Tue May 02, 2017 1:30 am UTC

Meteoric wrote:Here's where I mash up k and (k + 1), for some reason, which strikes me as assuming both k and (k + 1).

1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1)
This isn't an assumption. The line above was an assumption, but given that assumption, this is a totally valid step: you're adding (k+1) to both sides.



Aha! That's something that I don't understand - why is it that I'm allowed to push (k + 1) onto both sides of the equation?

Here's another part that feels like cheating, where I substitute the right side of the first equation for part of the left side of a later one.

k(k + 1)/2 + (k + 1) = k(k + 1)/2 + (k + 1)
I don't think this is what you want to do. You want to end up with an equation that says "the sum of 1 through (k+1) is this nice expression". If you do this step, you no longer have the part about the sum of 1 through (k+1).

Instead, you take your left-hand side, and you leave it completely alone. 1+2+3+...+k+(k+1) is exactly what you want over there.

On your right-hand side, you do some algebra to show that k(k+1)/2 + (k+1) is actually the same thing as (k+1)(k+2)/2.


This is my other big hang-up in execution - why do I leave the left side alone, and what is the significance of (k + 1)(k + 2)/2?

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Qaanol » Tue May 02, 2017 1:32 am UTC

MathDoofus wrote:But how does "assume A, therefore B" prove anything?

It proves that *if* you are on some rung of the ladder, *then* you can step up to the next rung.

You are right that it doesn’t say anything about whether you can reach the rung you are assuming to start on, it just says that *if* you start there, then you can get to the next rung.

That is *all* you are trying to prove with the induction step. That *if* your statement is true about k, *then* it is also true about (k+1).

Suppose that you are able to do so. What does that mean? Well it means you can plug in any k and say “If my statement is true about k, then it is also true about (k+1).”

Where does that get you? Well, you can plug in n=4 and say, “If my statement is true about 4, then it is also true about 5.”

And, “If my statement is true about 5, then it is also true about 6.”

And, “If my statement is true about 6, then it is also true about 7.”

And so forth.

MathDoofus wrote:Here's where I'm confused:

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

We take this as a given. We assume it is true for some k.

MathDoofus wrote:Here's where I mash up k and (k + 1), for some reason, which strikes me as assuming both k and (k + 1).

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

All you have done here is add (k+1) to both sides of the previous equation. Perfectly valid.

MathDoofus wrote: Here's another part that feels like cheating, where I substitute the right side of the first equation for part of the left side of a later one.

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

Below is where I get stuck on the algebra and how to "solve" this equation.

(k^2 + k)/2 + (k + 1) = (k^2 + k)/2 + (k + 1)

Ah, you seem to misunderstand the goal here. You are not trying to “solve” that equation. You are trying to show that the thing you started with, (1+2+3+…+k+(k+1)), has the same value as the thing you *think* it should equal, namely your statement with (k+1) plugged in.

In other words, you need to manipulate (1+2+3+…+k+(k+1)) with valid operations which do not change its value, until it ends up in the form n(n+1)/2 with n=(k+1).

And the only thing you know about k is that (1+2+3+…+k) = k(k+1)/2.

You are trying to show that *if* the formula works for n=k, *then* the formula also works with n=(k+1). That is how you step up the ladder. Assume you are on rung k, and prove that *if* you are on rung k, *then* you can reach rung (k+1).
wee free kings

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:35 am UTC

Qaanol wrote:

And the only thing you know about k is that (1+2+3+…+k) = k(k+1)/2.

You are trying to show that *if* the formula works for n=k, *then* the formula also works with n=(k+1). That is how you step up the ladder. Assume you are on rung k, and prove that *if* you are on rung k, *then* you can reach rung (k+1).


That's another thing that I don't get - how is it that what I "know about k" is that (1 + 2 + 3 + ... + k) = k(k+1)/2? Am I not just assuming that, as opposed to knowing it?

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 1:39 am UTC

MathDoofus wrote:Aha! That's something that I don't understand - why is it that I'm allowed to push (k + 1) onto both sides of the equation?

When you have an equation, you are allowed to add anything you want to both sides.
This is my other big hang-up in execution - why do I leave the left side alone, and what is the significance of (k + 1)(k + 2)/2?

To make the induction work, you need to show that P(k) implies P(k+1).

P(k) is the premise that you assumed, which reads "1+2+...+k=k(k+1)/2".

P(k+1) is the statement "1+2+...+k+(k+1)=(k+1)(k+2)/2". You DON'T get to assume this, but you want to prove it - so you take some other equation and manipulate it until it looks like this.

That's the reason we chose to add (k+1) to both sides: it makes the left side look like we want. But on the right side, we have

k(k+1)/2+(k+1)

while we want

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

Once we can show that these are actually the same thing, we're done.
No, even in theory, you cannot build a rocket more massive than the visible universe.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Qaanol » Tue May 02, 2017 1:42 am UTC

MathDoofus wrote:That's another thing that I don't get - how is it that what I "know about k" is that (1 + 2 + 3 + ... + k) = k(k+1)/2? Am I not just assuming that, as opposed to knowing it?

You know that about k because you assume it about k. You are proving something about *every* number k for which (1+2+3+…k) = k(k+1)/2.

If k is *any* number for which (1+2+3+…+k) = k(k+1)/2, then what can you say about (k+1)?
wee free kings

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:44 am UTC

Meteoric wrote:That's the reason we chose to add (k+1) to both sides: it makes the left side look like we want. But on the right side, we have

k(k+1)/2+(k+1)

while we want

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

Once we can show that these are actually the same thing, we're done.


I don't understand why we want "(k + 1)(k + 2)/2" on the right side. What am I missing?

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:45 am UTC

Qaanol wrote:
MathDoofus wrote:That's another thing that I don't get - how is it that what I "know about k" is that (1 + 2 + 3 + ... + k) = k(k+1)/2? Am I not just assuming that, as opposed to knowing it?

You know that about k because you assume it about k. You are proving something about *every* number k for which (1+2+3+…k) = k(k+1)/2.

If k is *any* number for which (1+2+3+…+k) = k(k+1)/2, then what can you say about (k+1)?


I'm not sure what you're asking, my apologies. In particular, I don't know how we're proving the (k + 1) case by assuming both the (k) case and the (k + 1) case.

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 1:48 am UTC

MathDoofus wrote:I don't understand why we want "(k + 1)(k + 2)/2" on the right side. What am I missing?

That's the statement that you are trying to prove.

You want to show that for any n, 1+2+...+n=n(n+1)/2. In particular, in the case when n=(k+1), this should mean that 1+2+...+(k+1)=(k+1)((k+1)+1)/2. That's the statement I called P(k+1), which you need to show is implied by P(k).

Honestly, the more we work on this problem, the more I think this is absolutely terrible as a first example of induction - you're dealing not just with the induction itself, but also complicated expressions and lots of algebra.
No, even in theory, you cannot build a rocket more massive than the visible universe.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Qaanol » Tue May 02, 2017 1:50 am UTC

MathDoofus wrote:I don't understand why we want "(k + 1)(k + 2)/2" on the right side. What am I missing?

What does the statement “(1+2+3+…+n) = n(n+1)/2” say when n=(k+1)?

MathDoofus wrote:I'm not sure what you're asking, my apologies. In particular, I don't know how we're proving the (k + 1) case by assuming both the (k) case and the (k + 1) case.

We are not assuming the n=(k+1) case. We are only assuming the n=k case, and we are proving that *if* the n=k case works, *then* the n=(k+1) case also works.

Another way to think about it is that we are only considering values of k for which (1+2+3+…+k) = k(k+1)/2.

In other words, let k be any number such that (1+2+3+…+k) = k(k+1)/2. Now, for all such numbers k where that formula holds, what can we prove about (k+1)?
wee free kings

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:53 am UTC

Meteoric wrote:
MathDoofus wrote:I don't understand why we want "(k + 1)(k + 2)/2" on the right side. What am I missing?

That's the statement that you are trying to prove.

You want to show that for any n, 1+2+...+n=n(n+1)/2. In particular, in the case when n=(k+1), this should mean that 1+2+...+(k+1)=(k+1)((k+1)+1)/2. That's the statement I called P(k+1), which you need to show is implied by P(k).

Honestly, the more we work on this problem, the more I think this is absolutely terrible as a first example of induction - you're dealing not just with the induction itself, but also complicated expressions and lots of algebra.


I thought that we were trying to prove that 1 + 2 + 3 + ... n = n(n + 1)/2

Plugging in (k + 1) leaves me with:

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

Is that incorrect? Now I'm thoroughly confused!

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:55 am UTC

Qaanol wrote:We are not assuming the n=(k+1) case. We are only assuming the n=k case, and we are proving that *if* the n=k case works, *then* the n=(k+1) case also works.

Another way to think about it is that we are only considering values of k for which (1+2+3+…+k) = k(k+1)/2.

In other words, let k be any number such that (1+2+3+…+k) = k(k+1)/2. Now, for all such numbers k where that formula holds, what can we prove about (k+1)?


I don't understand how we're not assuming both the k case and the (k + 1) case at the same time - isn't that what all of the algebraic manipulations are about? Can you explain what you're getting at using different words? I'm sorry; I'm just not understanding your answer or your question about (k + 1).
Last edited by MathDoofus on Tue May 02, 2017 1:56 am UTC, edited 1 time in total.

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 1:55 am UTC

[Mistaken double post, my apologies].

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 1:57 am UTC

MathDoofus wrote:I thought that we were trying to prove that 1 + 2 + 3 + ... n = n(n + 1)/2

Plugging in (k + 1) leaves me with:

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

Is that incorrect? Now I'm thoroughly confused!

No you're not, you've got it exactly right. But notice that the part I've underlined could also be written (k+2). So you've got the same thing I do.

Our overall goal is to prove this for every n, but our sub-goal at this step of the induction proof is to prove it for (k+1) specifically.
No, even in theory, you cannot build a rocket more massive than the visible universe.

User avatar
Sizik
Posts: 1190
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Mathematical Induction - Introductory Question

Postby Sizik » Tue May 02, 2017 1:57 am UTC

It might be easier to understand if we use a function: f(n) = n(n+1)/2
We want to prove the equation "1+2+...+n = f(n), for all integers n >= 4"

We start by calculating that f(4) = 4(5)/2 = 10 = 1+2+3+4, so we've proved it for n = 4.

We now want to prove the statement "If 1+2+...+k = f(k) for some k, then 1+2+...+k+(k+1) = f(k+1)". To do this, we have to be able to derive the second part (after "then") by assuming that the first part (after "if") is true.

Proof:

1+2+...+k = f(k)
(our assumption)

1+2+...+k+(k+1) = f(k) + (k+1)
(add (k+1) to both sides)

1+2+...+k+(k+1) = k(k+1)/2 + (k+1)
(expanding the definition of f)

... = k(k+1)/2 + 2(k+1)/2
(multiply the (k+1) by 2/2, and I'm omitting repeating the "1+2+...+k+(k+1)", since that side of the equation matches what we're trying to derive)

... = ( k(k+1) + 2(k+1) )/2
(adding the fractions)

... = (k+1)(k+2)/2
(factoring out (k+1))

... = (k+1)((k+1)+1)/2
(separating out (k+2) into ((k+1)+1))

... = f(k+1)
(definition of f)

So, we've now shown that given "1+2+...+k = f(k)", we can derive that "1+2+...+k+(k+1) = f(k+1)". This completes the induction step.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 2:00 am UTC

Meteoric wrote:
MathDoofus wrote:I thought that we were trying to prove that 1 + 2 + 3 + ... n = n(n + 1)/2

Plugging in (k + 1) leaves me with:

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

Is that incorrect? Now I'm thoroughly confused!

No you're not, you've got it exactly right. But notice that the part I've underlined could also be written (k+2). So you've got the same thing I do.

Our overall goal is to prove this for every n, but our sub-goal at this step of the induction proof is to prove it for (k+1) specifically.


Gotcha - thank you. So what's the next step that I'm missing?

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 2:01 am UTC

Sizik wrote:It might be easier to understand if we use a function: f(n) = n(n+1)/2
We want to prove the equation "1+2+...+n = f(n), for all integers n >= 4"



I appreciate this effort, but function notation adds (for me) an additional layer of complexity/confusion. I generally don't get function notation; I'm sorry. This re-writing of the problem appears much more complicated than the original.

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 2:05 am UTC

MathDoofus wrote:Gotcha - thank you. So what's the next step that I'm missing?

Show that

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

Once you do that, you put it together with the previous step and have

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

and if you cut out the middle, that's exactly what you were trying to show (in the induction 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

Postby MathDoofus » Tue May 02, 2017 2:08 am UTC

Meteoric wrote:
MathDoofus wrote:Gotcha - thank you. So what's the next step that I'm missing?

Show that

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

Once you do that, you put it together with the previous step and have

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

and if you cut out the middle, that's exactly what you were trying to show (in the induction step).


I don't understand - the k(k + 1)/2 part is what I was originally trying to prove, so why am I allowed to move that to the left-hand side of the equation?

And what do you mean by "put it together with the previous step"?

Finally, what do you mean by "cut out the middle"? I'm stumped by what I have to show in the final instance.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Qaanol » Tue May 02, 2017 2:09 am UTC

MathDoofus wrote:I don't understand how we're not assuming both the k case and the (k + 1) case at the same time - isn't that what all of the algebraic manipulations are about? Can you explain what you're getting at using different words? I'm sorry; I'm just not understanding your answer or your question about (k + 1).

If we were assuming the n=(k+1) case then we wouldn’t need any algebraic manipulation at all, we would just assume it to be true.

But we are not assuming it.

We are assuming the n=k case, and then using algebra to try to prove the n=(k+1) case.

In other words, let k be any number for which the statement in question is true when n=k. Now, given that, can you prove the statement is *also* true when n=(k+1)?
wee free kings

User avatar
Sizik
Posts: 1190
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Mathematical Induction - Introductory Question

Postby Sizik » Tue May 02, 2017 2:10 am UTC

MathDoofus wrote:
Sizik wrote:It might be easier to understand if we use a function: f(n) = n(n+1)/2
We want to prove the equation "1+2+...+n = f(n), for all integers n >= 4"



I appreciate this effort, but function notation adds (for me) an additional layer of complexity/confusion. I generally don't get function notation; I'm sorry. This re-writing of the problem appears much more complicated than the original.


My reason for attempting this is to separate out the expression we're trying to prove (n(n+1)/2) from the specific instance of that expression (e.g. (k+1)(k+2)/2, which is n(n+1)/2 with n replaced by (k+1)), so that it's easier to see that we've properly reached the end of the induction step (deriving the f(k+1) case from the f(k) case).
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 2:11 am UTC

Qaanol wrote:
MathDoofus wrote:I don't understand how we're not assuming both the k case and the (k + 1) case at the same time - isn't that what all of the algebraic manipulations are about? Can you explain what you're getting at using different words? I'm sorry; I'm just not understanding your answer or your question about (k + 1).

If we were assuming the n=(k+1) case then we wouldn’t need any algebraic manipulation at all, we would just assume it to be true.

But we are not assuming it.

We are assuming the n=k case, and then using algebra to try to prove the n=(k+1) case.

In other words, let k be any number for which the statement in question is true when n=k. Now, given that, can you prove the statement is *also* true when n=(k+1)?


But how can it be that assuming the n = k case proves the n = (k + 1) case? I'm more confused now than before, I'm afraid.

User avatar
ConMan
Shepherd's Pie?
Posts: 1658
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Mathematical Induction - Introductory Question

Postby ConMan » Tue May 02, 2017 2:13 am UTC

Whenever a mathematician says "Assume x", it means "Let us temporarily step into a universe where x is known to be true, and see what we can prove.". In the case of induction, we say "Assume that the statement is true for some particular value of n.", so we are stepping into a universe where we already know a true, but arbitrary, value for which the statement holds. Everything we prove then is dependent on being in that universe. In particular, when we prove "The statement is true for n+1", we are actually saying "In a universe where the statement is true for n, it is also true for n+1".

Once we step out of the assumption - out of the universe where we've assumed something about the truth of the statement - we can keep the thing we proved, but only conditional on the assumption. So what we have is the conditional statement "If the statement is true for some value of n, then it is also true for n+1."

The point of the "base case" proof is to show that we do live in such a universe. In the case of proving triangular numbers, for example, then you show that 1 = 1*(1+1)/2, so we live in a universe where S(1) is true.

Then we combine the two things we proved - we live in a universe where S(n) is true for the value n=1. And if S(n) is true for some n, then S(n+1) is also true. So therefore, setting n=1, we can say that since S(1) is true, S(1+1) = S(2) is also true. Which means we live in a universe where S(n) is true for n=2. So therefore, setting n=2, we can say that since S(2) is true, S(2+1) = S(3) is true. Which means we live in a universe where S(n) is true for n=3. And we can just keep going. And the axiom of induction just says that we're allowed to do that as many times as we need to reach any value of n>1, and so S(n) is true for all values of n.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
Sizik
Posts: 1190
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Mathematical Induction - Introductory Question

Postby Sizik » Tue May 02, 2017 2:15 am UTC

MathDoofus wrote:But how can it be that assuming the n = k case proves the n = (k + 1) case? I'm more confused now than before, I'm afraid.


I'll repost my earlier post without functions this time:

1+2+...+k = k(k+1)/2
(our assumption, the n=k case)

1+2+...+k+(k+1) = k(k+1)/2 + (k+1)
(add (k+1) to both sides)

... = k(k+1)/2 + 2(k+1)/2
(multiply the (k+1) by 2/2, and I'm omitting repeating the "1+2+...+k+(k+1)", since that side of the equation matches what we're trying to derive)

... = ( k(k+1) + 2(k+1) )/2
(adding the fractions)

... = (k+1)(k+2)/2
(factoring out (k+1))

... = (k+1)((k+1)+1)/2
(separating out (k+2) into ((k+1)+1))

1+2+...+k+(k+1) = (k+1)((k+1)+1)/2
(showing the left side again, this is the n=(k+1) case)

As shown above, if we start with the n=k case, we can algebraically manipulate it to produce the n=(k+1) case.
Last edited by Sizik on Tue May 02, 2017 2:16 am UTC, edited 1 time in total.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 2:16 am UTC

MathDoofus wrote:
Meteoric wrote:
MathDoofus wrote:Gotcha - thank you. So what's the next step that I'm missing?

Show that

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

Once you do that, you put it together with the previous step and have

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

and if you cut out the middle, that's exactly what you were trying to show (in the induction step).


I don't understand - the k(k + 1)/2 part is what I was originally trying to prove, so why am I allowed to move that to the left-hand side of the equation?

And what do you mean by "put it together with the previous step"?

Finally, what do you mean by "cut out the middle"? I'm stumped by what I have to show in the final instance.

Sorry, this is why one has to be careful about colloquial language in mathematics!

You started by assuming that

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

And then you added (k+1) to both sides to deduce

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

This is what I mean by "the previous step". Now the colors are to make my next step more clear: from there, you do some algebra to show that

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

Since red = blue and blue = green, you can "cut out the middle" (namely, blue) to conclude that red = green. They're both equal to blue, so they're equal to each other!

That completes the induction step: it shows that if 1+2+...+k=k(k+1)/2, then 1+2+...+(k+1)=(k+1)(k+2)/2. In words - if the k case is true, then the k+1 case is true too.
Last edited by Meteoric on Tue May 02, 2017 2:19 am UTC, edited 2 times in total.
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

Postby MathDoofus » Tue May 02, 2017 2:16 am UTC

Sizik wrote:
... = ( k(k+1) + 2(k+1) )/2
(adding the fractions)

... = (k+1)(k+2)/2
(factoring out (k+1))

... = (k+1)((k+1)+1)/2
(separating out (k+2) into ((k+1)+1))

1+2+...+k+(k+1) = (k+1)((k+1)+1)/2
(showing the left side again, this is the n=(k+1) case)


Thank you. But isn't your final step just the result of plugging in (k + 1) to both sides of the equation? Where would I go from there, and what (assuming I can get there) would I have proved?

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

Re: Mathematical Induction - Introductory Question

Postby MathDoofus » Tue May 02, 2017 2:19 am UTC

Meteoric wrote:

That completes the induction step: it shows that if 1+2+...+k=k(k+1)/2, then 1+2+...+(k+1)=(k+1)(k+2)/2. In words - if the k case is true, then the k+1 case is true too.


I don't understand how that proof comes about. It looks as though I've assumed both the k case and the (k + 1) case, and it's difficult to see how I can prove anything from assuming both of those things.

User avatar
Sizik
Posts: 1190
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Mathematical Induction - Introductory Question

Postby Sizik » Tue May 02, 2017 2:22 am UTC

MathDoofus wrote:
Sizik wrote:
... = ( k(k+1) + 2(k+1) )/2
(adding the fractions)

... = (k+1)(k+2)/2
(factoring out (k+1))

... = (k+1)((k+1)+1)/2
(separating out (k+2) into ((k+1)+1))

1+2+...+k+(k+1) = (k+1)((k+1)+1)/2
(showing the left side again, this is the n=(k+1) case)


Thank you. But isn't your final step just the result of plugging in (k + 1) to both sides of the equation? Where would I go from there, and what (assuming I can get there) would I have proved?


It is, and that's what we're trying to prove. We've proved that if we start with the fact that the equation is true when k is plugged in, we can show that the equation is also true when k+1 is plugged in.
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
Qaanol
The Cheshirest Catamount
Posts: 3055
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Mathematical Induction - Introductory Question

Postby Qaanol » Tue May 02, 2017 2:24 am UTC

MathDoofus wrote:But how can it be that assuming the n = k case proves the n = (k + 1) case? I'm more confused now than before, I'm afraid.

Okay, I think we are making progress now.

Proof by induction is not magic. The n=k case doesn’t *automatically* prove the n=(k+1) case. There are plenty of statements for which it *doesn’t* work.

But *if* you can use the n=k case to prove that the n=(k+1) case works, *then* you have a proof by induction.

You still have to do the work. You have to figure out how to get from the n=k case to the n=(k+1) case. You have to provide all the steps to get from one rung of the ladder to the next.

That is where the algebra part comes in here.

You know that the formula works for some number k. Now you have to show that it *also* works for (k+1). This is the induction step. It is not magic, you actually have to do the work to prove it.
wee free kings

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 2:25 am UTC

MathDoofus wrote:I don't understand how that proof comes about. It looks as though I've assumed both the k case and the (k + 1) case, and it's difficult to see how I can prove anything from assuming both of those things.

An assumption is a statement taken as true without justification. There's only one such statement in my post above: at the beginning, where we assumed the k case.

Every step after that has a specific justification. First we used the rule "if you add the same thing to both sides of an equation, it's still equal". Second, we used the rules of algebra to rearrange an expression. Third and last, we used the rule called transitivity - if two things are equal to the same thing, they are equal to each other.

I can go through and label each step with its justification, if it helps.
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

Postby MathDoofus » Tue May 02, 2017 2:34 am UTC

Meteoric wrote:
MathDoofus wrote:I don't understand how that proof comes about. It looks as though I've assumed both the k case and the (k + 1) case, and it's difficult to see how I can prove anything from assuming both of those things.

An assumption is a statement taken as true without justification. There's only one such statement in my post above: at the beginning, where we assumed the k case.

Every step after that has a specific justification. First we used the rule "if you add the same thing to both sides of an equation, it's still equal". Second, we used the rules of algebra to rearrange an expression. Third and last, we used the rule called transitivity - if two things are equal to the same thing, they are equal to each other.

I can go through and label each step with its justification, if it helps.


Yes, I think that would be helpful. Thank you!

My next question - why aren't the base case and a base-case-plus-one case enough? Why must we fool around with a k case?

User avatar
ConMan
Shepherd's Pie?
Posts: 1658
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Mathematical Induction - Introductory Question

Postby ConMan » Tue May 02, 2017 2:41 am UTC

MathDoofus wrote:
Meteoric wrote:
MathDoofus wrote:I don't understand how that proof comes about. It looks as though I've assumed both the k case and the (k + 1) case, and it's difficult to see how I can prove anything from assuming both of those things.

An assumption is a statement taken as true without justification. There's only one such statement in my post above: at the beginning, where we assumed the k case.

Every step after that has a specific justification. First we used the rule "if you add the same thing to both sides of an equation, it's still equal". Second, we used the rules of algebra to rearrange an expression. Third and last, we used the rule called transitivity - if two things are equal to the same thing, they are equal to each other.

I can go through and label each step with its justification, if it helps.


Yes, I think that would be helpful. Thank you!

My next question - why aren't the base case and a base-case-plus-one case enough? Why must we fool around with a k case?

Let's try with a fairly simple statement - "All numbers are less than 3.", or in a functional notation, "S(n): n < 3".

Test the base case, S(1). Is 1 less than 3? Yes. Cool, base case proven.

Test the base-case-plus one, S(1+1) = S(2). Is 2 less than 3? Yes, base-case-plus-one is also proven.

But that doesn't help us prove the statement true for all numbers. In fact, the statement is false for the very next case, S(3).
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

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

Re: Mathematical Induction - Introductory Question

Postby Meteoric » Tue May 02, 2017 2:45 am UTC

Here are the pieces of the induction step:

  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]

As you can see, step 1 is an assumption, but the others are deduced with ordinary rules of math. Step 3 could be written out as multiple steps to show your work, if you prefer.
Last edited by Meteoric on Tue May 02, 2017 2:47 am UTC, edited 2 times in total.
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

Postby MathDoofus » Tue May 02, 2017 2:46 am UTC

ConMan wrote:
MathDoofus wrote:
Meteoric wrote:
MathDoofus wrote:I don't understand how that proof comes about. It looks as though I've assumed both the k case and the (k + 1) case, and it's difficult to see how I can prove anything from assuming both of those things.

An assumption is a statement taken as true without justification. There's only one such statement in my post above: at the beginning, where we assumed the k case.

Every step after that has a specific justification. First we used the rule "if you add the same thing to both sides of an equation, it's still equal". Second, we used the rules of algebra to rearrange an expression. Third and last, we used the rule called transitivity - if two things are equal to the same thing, they are equal to each other.

I can go through and label each step with its justification, if it helps.


Yes, I think that would be helpful. Thank you!

My next question - why aren't the base case and a base-case-plus-one case enough? Why must we fool around with a k case?

Let's try with a fairly simple statement - "All numbers are less than 3.", or in a functional notation, "S(n): n < 3".

Test the base case, S(1). Is 1 less than 3? Yes. Cool, base case proven.

Test the base-case-plus one, S(1+1) = S(2). Is 2 less than 3? Yes, base-case-plus-one is also proven.

But that doesn't help us prove the statement true for all numbers. In fact, the statement is false for the very next case, S(3).


Again, I don't understand functional notation at all (have always found it hopelessly confusing). But how does the k case ensure that we don't make the mistake you describe above? Seems like the k step could be dispensed with.


Return to “Mathematics”

Who is online

Users browsing this forum: ThirdParty and 6 guests