Mathematical Induction - Introductory Question

[WibblyWobbly]

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

First, some terminology. You didn't "plug in" (k+1) to both sides, you added it to both sides. "Plugging in" is the same as substitution, and you don't want to substitute anything here. Now, when you added (k+1) to both sides, what you're doing is actually writing the (k+1)-case directly from the k-case - it just looks a little different than if you had substituted (k+1) for n in the original equation (which is also the (k+1)-case). That's actually what we're trying to prove: that adding (k+1) to both sides of the k-case equation gives you the equation for the (k+1)-case.

[MathDoofus]

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.

I don't even know where to begin analyzing the even-odd example that you've suggested. Although I appreciate the suggestion, I at least have the skeleton (however flimsy) of this problem to work on. I can't walk away after investing so many hours to understanding this one.

[MathDoofus]

First, some terminology. You didn't "plug in" (k+1) to both sides, you added it to both sides. "Plugging in" is the same as substitution, and you don't want to substitute anything here. Now, when you added (k+1) to both sides, what you're doing is actually writing the (k+1)-case directly from the k-case - it just looks a little different than if you had substituted (k+1) for n in the original equation (which is also the (k+1)-case). That's actually what we're trying to prove: that adding (k+1) to both sides of the k-case equation gives you the equation for the (k+1)-case.

OK. So I'm at step 2/equation 2, where I've (k + 1) to both sides to connect up the k case and the (k + 1) case (as you've pointed out, it makes sense that they'd be connected--at least it makes sense in an abstract way--because (k + 1) is the next step up from the k case).

Here's what I have at that step:

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

Where should I go from there, and what's the rationale for doing so?

[Meteoric]

The outline of an induction proof always looks like this:

BASE STEP: 1 is either even or odd, because [???]

INDUCTION STEP: Assume that k is either even or odd. Then [???], so k+1 is either even or odd.

What should go in the [???] boxes?

[MathDoofus]

The outline of an induction proof always looks like this:

BASE STEP: 1 is either even or odd, because [???]

INDUCTION STEP: Assume that k is either even or odd. Then [???], so k+1 is either even or odd.

What should go in the [???] boxes?

Like I said, I have no idea how to even begin analyzing this one.

[Meteoric]

Look at the base step. Is 1 even or odd?

[MathDoofus]

Look at the base step. Is 1 even or odd?

I don't know that it's even or odd. If I had to make something up, I'd say that the even natural numbers are those divisible by two with no remainder, and the odds are everything else.

[Meteoric]

Okay, so according to that definition, is 1 even, or is it odd?

And if I wanted to be pedantic, would it be valid to just answer "yes"?

[WibblyWobbly]

First, some terminology. You didn't "plug in" (k+1) to both sides, you added it to both sides. "Plugging in" is the same as substitution, and you don't want to substitute anything here. Now, when you added (k+1) to both sides, what you're doing is actually writing the (k+1)-case directly from the k-case - it just looks a little different than if you had substituted (k+1) for n in the original equation (which is also the (k+1)-case). That's actually what we're trying to prove: that adding (k+1) to both sides of the k-case equation gives you the equation for the (k+1)-case.

OK. So I'm at step 2/equation 2, where I've (k + 1) to both sides to connect up the k case and the (k + 1) case (as you've pointed out, it makes sense that they'd be connected--at least it makes sense in an abstract way--because (k + 1) is the next step up from the k case).

Here's what I have at that step:

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

Where should I go from there, and what's the rationale for doing so?

So what you have on that next-to-last line is the (k+1)-case. You connected it up from the k-case. That was what we wanted to do.

But we can also get the (k+1)-case directly from the original equation:
1 + 2 + 3 + ... + n = n(n+1)/2
if we substitute (k+1) for n:
1 + 2 + 3 + ... + k + (k+1) = [(k+1)((k+1)+1)]/2

If both of these are the (k+1)-case, they should look the same, right? They should be identical, term for term, on each side of the equals sign.
Looks good on the left-hand sides, right? 1 + 2 + 3 + ... + k + (k+1) is the same as 1 + 2 + 3 + ... + k + (k+1).

But the right-hand sides don't really look the same.
Does k(k + 1)/2 + (k + 1) = [(k+1)((k+1)+1)]/2? Expand out both sides and show that it does.

Then, 1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) will be equivalent to 1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1)]/2

This would mean that the (k+1)-case you got from substituting (k+1) for n in the original equation is the same as the (k+1)-case you got from the k-case. This means that the k-case implies the (k+1)-case, or equivalently, it means that we have proven that if the k-case is true, the (k+1)-case is true. Which is what we need for the induction step. Combine that with the base case, and we're finished.

[MathDoofus]

Okay, so according to that definition, is 1 even, or is it odd?

And if I wanted to be pedantic, would it be valid to just answer "yes"?

We could answer "yes" and be correct but that wouldn't yield any meaningful information.

[Meteoric]

Okay, so according to that definition, is 1 even, or is it odd?

And if I wanted to be pedantic, would it be valid to just answer "yes"?

We could answer "yes" and be correct but that wouldn't yield any meaningful information.

Right, but it would show that the base step holds. In particular, 1 is odd, so it is "either even or odd".

In the induction step, we have a number k, which is either even or odd.

If k is even, what about k+1?

If k is odd, what about k+1?

[MathDoofus]

So what you have on that next-to-last line is the (k+1)-case. You connected it up from the k-case. That was what we wanted to do.

But we can also get the (k+1)-case directly from the original equation:
1 + 2 + 3 + ... + n = n(n+1)/2
if we substitute (k+1) for n:
1 + 2 + 3 + ... + k + (k+1) = [(k+1)((k+1)+1)]/2

If both of these are the (k+1)-case, they should look the same, right? They should be identical, term for term, on each side of the equals sign.
Looks good on the left-hand sides, right? 1 + 2 + 3 + ... + k + (k+1) is the same as 1 + 2 + 3 + ... + k + (k+1).

This is something that I don't get - why is it that "we can . . . get the (k + 1) case directly from the original equation," and what does that statement even mean? How would a person know that, or even think to do that? And what's the purpose of doing so?

But the right-hand sides don't really look the same.
Does k(k + 1)/2 + (k + 1) = [(k+1)((k+1)+1)]/2? Expand out both sides and show that it does.

Then, 1 + 2 + 3 + ... + k + (k + 1) = k(k + 1)/2 + (k + 1) will be equivalent to 1 + 2 + 3 + ... + k + (k + 1) = [(k+1)((k+1)+1)]/2

This would mean that the (k+1)-case you got from substituting (k+1) for n in the original equation is the same as the (k+1)-case you got from the k-case. This means that the k-case implies the (k+1)-case, or equivalently, it means that we have proven that if the k-case is true, the (k+1)-case is true. Which is what we need for the induction step. Combine that with the base case, and we're finished.

Once I've grasped the first part of your explanation, then I'll try to tackle the rest.

[MathDoofus]

Okay, so according to that definition, is 1 even, or is it odd?

And if I wanted to be pedantic, would it be valid to just answer "yes"?

We could answer "yes" and be correct but that wouldn't yield any meaningful information.

Right, but it would show that the base step holds. In particular, 1 is odd, so it is "either even or odd".

In the induction step, we have a number k, which is either even or odd.

If k is even, what about k+1?

If k is odd, what about k+1?

We know that adding one makes an even number an odd number, and vice versa.

[Meteoric]

Great! Then since k is either even or odd, we know that k+1 is odd (in the first case) or even (in the second case). That is, k+1 is either even or odd.

That's the induction step. We took a fact about k, and used it to demonstrate a fact about k+1.

[MathDoofus]

Great! Then since k is either even or odd, we know that k+1 is odd (in the first case) or even (in the second case). That is, k+1 is either even or odd.

That's the induction step. We took a fact about k, and used it to demonstrate a fact about k+1.

Yes, but I don't understand how that's an example of proof by induction. I haven't shown anything for k or (k + 1), only for examples (here, 1) that I've selected at random.

[WibblyWobbly]

So what you have on that next-to-last line is the (k+1)-case. You connected it up from the k-case. That was what we wanted to do.

But we can also get the (k+1)-case directly from the original equation:
1 + 2 + 3 + ... + n = n(n+1)/2
if we substitute (k+1) for n:
1 + 2 + 3 + ... + k + (k+1) = [(k+1)((k+1)+1)]/2

If both of these are the (k+1)-case, they should look the same, right? They should be identical, term for term, on each side of the equals sign.
Looks good on the left-hand sides, right? 1 + 2 + 3 + ... + k + (k+1) is the same as 1 + 2 + 3 + ... + k + (k+1).

This is something that I don't get - why is it that "we can . . . get the (k + 1) case directly from the original equation," and what does that statement even mean? How would a person know that, or even think to do that? And what's the purpose of doing so?

It's because your original goal, in all of this induction, is to prove that there is a nice, simple formula for finding the sum of the first n positive integers. That formula is n(n+1)/2. You're trying to prove this is true for all positive integers, right?

k is just a positive integer.
k+1 is just a (different) positive integer.

We get the k-case by substituting k for n in n(n+1)/2, right? So why can't we get the (k+1)-case from substituting (k+1) for n in n(n+1)/2, too? The answer is that we can.

[Meteoric]

Great! Then since k is either even or odd, we know that k+1 is odd (in the first case) or even (in the second case). That is, k+1 is either even or odd.

That's the induction step. We took a fact about k, and used it to demonstrate a fact about k+1.

Yes, but I don't understand how that's an example of proof by induction. I haven't shown anything for k or (k + 1), only for examples (here, 1) that I've selected at random.

Well, let's go back to the outline above, and fill in the parts we just wrote:

BASE STEP: 1 is either even or odd, in particular, it's odd.

INDUCTION STEP: Assume that k is either even or odd. If k is even, then k+1 is odd. If k is odd, then k+1 is even. So either way, k+1 is either even or odd.

That's it. That's the whole proof. You have now written a complete proof by induction.

[MathDoofus]

It's because your original goal, in all of this induction, is to prove that there is a nice, simple formula for finding the sum of the first n positive integers. That formula is n(n+1)/2. You're trying to prove this is true for all positive integers, right?

k is just a positive integer.
k+1 is just a (different) positive integer.

We get the k-case by substituting k for n in n(n+1)/2, right? So why can't we get the (k+1)-case from substituting (k+1) for n in n(n+1)/2, too? The answer is that we can.

Ah. Could we skip Step 1 (the k case) and proceed directly to the case in which we connect up the k case and the (k + 1) case? Also, I don't understand how Step 2 and (whatever step involves substituting (k + 1) for every instance of k is) interact. Can you explain that again? I feel like I've asked the question a thousand times but haven't received an answer on how these steps are related. Thank you.

[MathDoofus]

Great! Then since k is either even or odd, we know that k+1 is odd (in the first case) or even (in the second case). That is, k+1 is either even or odd.

That's the induction step. We took a fact about k, and used it to demonstrate a fact about k+1.

Yes, but I don't understand how that's an example of proof by induction. I haven't shown anything for k or (k + 1), only for examples (here, 1) that I've selected at random.

Well, let's go back to the outline above, and fill in the parts we just wrote:

BASE STEP: 1 is either even or odd, in particular, it's odd.

INDUCTION STEP: Assume that k is either even or odd. If k is even, then k+1 is odd. If k is odd, then k+1 is even. So either way, k+1 is either even or odd.

That's it. That's the whole proof. You have now written a complete proof by induction.

I don't understand how this relates to my original example that I've been wrestling with for two days. In particular, I know which numbers are odd and which are even; by contrast, if not for this example, it'd never occur to me that the sum of 1 + 2 + 3 + ... + n = n(n + 1)/2.

[Meteoric]

Ah. Could we skip Step 1 (the k case) and proceed directly to the case in which we connect up the k case and the (k + 1) case?

No, because step 1 is a part of the process of connecting those.

Also, I don't understand how Step 2 and (whatever step involves substituting (k + 1) for every instance of k is) interact. Can you explain that again? I feel like I've asked the question a thousand times but haven't received an answer on how these steps are related. Thank you.

It doesn't. There is no step where you substitute (k+1) for k.

I don't understand how this relates to my original example that I've been wrestling with for two days. In particular, I know which numbers are odd and which are even; by contrast, if not for this example, it'd never occur to me that the sum of 1 + 2 + 3 + ... + n = n(n + 1)/2.

It relates because it is an induction proof.

I agree that it is a very trivial induction proof. It does not address any of the problems you're having with algebra in the original problem. That is why I am also recommending that you practice algebra, separately, as an independent skill. Once you do that, you will find that the algebra is also very simple. Then all you'll have is simple algebra, and a simple proof structure, and so the whole thing will be easy.

Right now, you're having trouble because you don't understand the individual parts of the proof.

[MathDoofus]

I agree that it is a very trivial induction proof. It does not address any of the problems you're having with algebra in the original problem. That is why I am also recommending that you practice algebra, separately, as an independent skill. Once you do that, you will find that the algebra is also very simple. Then all you'll have is simple algebra, and a simple proof structure, and so the whole thing will be easy.

Right now, you're having trouble because you don't understand the individual parts of the proof.

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

[MathDoofus]

It's because your original goal, in all of this induction, is to prove that there is a nice, simple formula for finding the sum of the first n positive integers. That formula is n(n+1)/2. You're trying to prove this is true for all positive integers, right?

k is just a positive integer.
k+1 is just a (different) positive integer.

We get the k-case by substituting k for n in n(n+1)/2, right? So why can't we get the (k+1)-case from substituting (k+1) for n in n(n+1)/2, too? The answer is that we can.

Still at Step 2 and trying figure out which steps come next, and why:

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

Can you help with that?

[Meteoric]

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

The rungs in induction are always the natural numbers. Even/odd are not rungs.

You've proven that you can "stand on the first rung" (ie, 1 is either even or odd) and you can "get to the next rung" (ie, if k is either even or odd, then k+1 is either even or odd). That's induction.

[MathDoofus]

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

The rungs in induction are always the natural numbers. Even/odd are not rungs.

You've proven that you can "stand on the first rung" (ie, 1 is either even or odd) and you can "get to the next rung" (ie, if k is either even or odd, then k+1 is either even or odd). That's induction.

But this "proof" by induction simply instructs a person to add one to get to the next even or odd number. I haven't done anything to prove anything.

[Meteoric]

That IS the proof.

Suppose I claimed that, somewhere out past six billion, there is a number that is neither even (a multiple of 2) nor odd (a multiple of 2, plus 1). This proof by induction shows that isn't true: the number before it is either even or odd, so my number is either odd or even.

[MathDoofus]

That IS the proof.

Suppose I claimed that, somewhere out past six billion, there is a number that is neither even (a multiple of 2) nor odd (a multiple of 2, plus 1). This proof by induction shows that isn't true: the number before it is either even or odd, so my number is either odd or even.

I don't see how we've proved that exactly (obviously I know that natural numbers are either even or odd, but never both and never neither). Our k case and (k + 1) case don't tell anyone whether k or (k + 1) is even or odd.

[Demki]

It's a proof by induction of the statement "every natural number n is either even or odd"

Another, simpler(and pretty trivial) proof by induction would be "every positive natural number n is divisible by 1"

To prove that by induction, we follow the basic steps of induction:

Base case: 1 is trivially divisible by 1(you can check your calculator if you want)

Inductive step: we want to prove the following statement "if k is divisible by 1 then (k+1) is divisible by 1"
We prove that statement by assuming that k is divisible by 1 and showing that k+1 is divisible by 1:
1. k is divisible by 1 (premise)
2. 1 is divisible by 1 (base case)
3. The sum of 2 numbers divisible by some integer m is also divisible by m (you could try to prove this, if you want I'll post a proof of that, it is simple algebra with no induction)
4. k+1 is divisible by 1 (follows from statements 1, 2 and 3)
So we've shown that statement 1 implies statement 4, that is, we've shown "if k is divisible by 1 then (k+1) is divisible by 1"


We've shown both the base case and the inductive step, therefore we've produced a valid proof by induction that every positive natural number is divisible by 1. (Provided any positive natural number I can build a finite "ladder" from the base case and inductive steps to show that number is divisible by 1)


As others have said, I strongly suggest you leave the problem of the sum of the first n numbers alone for now, and go study algebra and logic and get a good grasp on both. Yes the problem isn't particularily hard, but what you are doing here is trying to tighten a screw with a broken screwdriver.

[Flumble]

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

We are assuming that the 'current' rung is either* even or odd. And we want to prove that therefore the 'next' rung must also be even or odd.
The reason we need to prove it, is that there's no 'basic' rule that says "if a number is even or odd, the successive number is even or odd", but we do have the basic rules "if a number is even, its successor is odd" and "if a number is odd, its successor is even". By splitting our reasoning about the current rung into its two alternatives, we can apply the basic rules and then merge them to a single answer to prove the next rung is indeed even or odd:

(the third step I took there is intuitively valid: when "I'm eating bread" is true, "I'm eating bread or the cat is on fire" is also true, regardless of whether the cat is on fire)


*well I like to weaken the statement to "even or odd", meaning it could also be both (because it's easier to say that a next rung is "even or odd", than to say it's "either even or odd"). If it's both, it definitely has the property of being even and you just take that alternative. Or you take the other alternative. Or you take both alternatives. It doesn't matter, since it always ends up with "k+1 is even or odd".

[MathDoofus]

I don't know how that counts as an induction proof. I've established only two alternatives, and not a single answer. In other words, there are two rungs and I haven't told anyone which rung we're actually on.

We are assuming that the 'current' rung is either even or odd. And we want to prove that therefore the 'next' rung must also be even or odd.
The reason we need to prove it, is that there's no 'basic' rule that says "if a number is even or odd, the successive number is even or odd", but we do have the basic rules "if a number is even, its successor is odd" and "if a number is odd, its successor is even". By splitting our reasoning about the current rung into its two alternatives, we can apply the basic rules and then merge them to a single answer to prove the next rung is indeed even or odd:
neveroddoreven.png
(the third step I took there is intuitively valid: when "I'm eating bread" is true, "I'm eating bread or the cat is on fire" is also true, regardless of whether the cat is on fire)

That intuitively valid step seems fine to me because of how "or" works. But I don't understand how the even or odd stuff amounts to a proof by induction.

[Meteoric]

You're struggling here for the same reason I've noted before: you don't seem to understand the difference between a conditional and its parts.

You CANNOT understand induction without first understanding conditionals. They're what induction is made of.

[MathDoofus]

You're struggling here for the same reason I've noted before: you don't seem to understand the difference between a conditional and its parts.

You CANNOT understand induction without first understanding conditionals. They're what induction is made of.

I can draft truth tables to test conditionals. I did take first order logic some years ago. Can someone help with my Step 2/Step 3 question above?

[Meteoric]

But you don't seem to know how to prove them, which is what we're doing here. We keep circling around this same problem. The induction step is just a conditional proof.

[MathDoofus]

But you don't seem to know how to prove them, which is what we're doing here. We keep circling around this same problem. The induction step is just a conditional proof.

If I demonstrate that a base case is true, and then demonstrate that if the k case is true then the (k + 1) case is true, then I've shown that the whole ball of wax is true.

[Demki]

But you don't seem to know how to prove them, which is what we're doing here. We keep circling around this same problem. The induction step is just a conditional proof.

If I demonstrate that a base case is true, and then demonstrate that if the k case is true then the (k + 1) case is true, then I've shown that the whole ball of wax is true.

So where's your problem with the proof by induction of the statement "every positive integer is even or it is odd"?

[Meteoric]

And how do you prove if-then statements? Like, can you prove "If n is even then n^2 is a multiple of 4"?

[MathDoofus]

And how do you prove if-then statements? Like, can you prove "If n is even then n^2 is a multiple of 4"?

You would assume that "n is even" is true, and then show that if that assumption is true, then the "n^2 is a multiple of 4" part must also be true.

[Meteoric]

Isn't that what I did above?

[Flumble]

But you don't seem to know how to prove them, which is what we're doing here. We keep circling around this same problem. The induction step is just a conditional proof.

If I demonstrate that a base case is true, and then demonstrate that if the k case is true then the (k + 1) case is true, then I've shown that the whole ball of wax is true.

Indeed, so that's why you can show with induction that every positive number is odd or even:

(click it for a readable size)


Induction may well be the weirdest way to prove that every positive number is odd or even (you'd rather directly prove for every number that, for example, when dividing by two, you end up with a remainder of 0 or 1, meaning it's even or odd), but it's one of the most accessible statements that can be proven with induction.

[MathDoofus]

Isn't that what I did above?

I don't see that.

[MathDoofus]

It's because your original goal, in all of this induction, is to prove that there is a nice, simple formula for finding the sum of the first n positive integers. That formula is n(n+1)/2. You're trying to prove this is true for all positive integers, right?

k is just a positive integer.
k+1 is just a (different) positive integer.

We get the k-case by substituting k for n in n(n+1)/2, right? So why can't we get the (k+1)-case from substituting (k+1) for n in n(n+1)/2, too? The answer is that we can.

Still at Step 2 and trying figure out which steps come next, and why:

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

Can you help with that?

Can anyone help me with this? Thank you.