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

Demki wrote:
MathDoofus wrote:
Meteoric wrote:Yes! That is a valid argument, and a perfect example of proof by induction. You have the base step, the induction step, and you correctly justify your conclusion using known properties of even and odd numbers.

But my argument still contains an assumption that I'd need to build out (I think), which is that every positive integer is either cleanly divisible by two or not. I'm not sure how I'd deal with in a proof by induction.

So instead of using the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number not divisible by 2
Use the definitions:
"Even" - a number cleanly divisible by 2
"Odd" - a number one greater than a number cleanly divisible by 2

This way you are tasked to prove that every integer that isn't even is odd.
The steps are basically the same as what you said earlier, just with a bit more justification as to why "an odd number + 1 is even"

I mean, clearly if we replace the 2s in these definitions with a 3, then the first set of definition still cover every integer, yet the second set doesn't (every integer of the form 3n+2 is missing)

And this is why it is important to state your definitions clearly.

Gotcha - thinking through this, however, I guess I haven't accounted for the case of 1, which is odd (I think) but doesn't get swept into the definition of "a number greater than a number cleanly divisible by 2," unless we count 0 as a number (but it's not a positive integer).

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

The even/odd definition I posted apply for all integers, not just the positive ones. 0 is a multiple of 2(2*0=0), therefore it is even. 0 is divisible by every number except 0.

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

### Re: Mathematical Induction - Introductory Question

Right, exactly. You're correct that if we take "odd" to mean "not even", then there's nothing to prove. But under the standard definition about 2m and 2m+1, it takes a little bit of justification.

Clearly, if I take 2m and add 1, then I've got 2m+1 which is odd. But what if I take 2m+1 and add 1? Then I've got 2m+2. Can I write that as "2 times some whole number"? That would show that an odd number plus 1 makes an even number.
No, even in theory, you cannot build a rocket more massive than the visible universe.

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

### Re: Mathematical Induction - Introductory Question

Meteoric wrote:Right, exactly. You're correct that if we take "odd" to mean "not even", then there's nothing to prove. But under the standard definition about 2m and 2m+1, it takes a little bit of justification.

Clearly, if I take 2m and add 1, then I've got 2m+1 which is odd. But what if I take 2m+1 and add 1? Then I've got 2m+2. Can I write that as "2 times some whole number"? That would show that an odd number plus 1 makes an even number.

That makes sense. I'm going to study the chart that shows how the even-odd problem fits into the induction rubric.

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

### Re: Mathematical Induction - Introductory Question

I've spent some time thinking about induction, and I've figured out that I don't have the algebra skills to complete any induction problem right now. I simply don't know the re-writing rules well enough to perform the symbol-magic to get at a solution. Nevertheless, can someone tell me why the proof below is different from what we've been doing in this thread?

Let's assume that S(n)=n*(n+1)/2
S(n+1)=Sum of first (n+1) terms
= Sum of first 'n' terms + (n+1)th term
= n*(n+1)/2 + (n+1)
= (n^2+n+2*n+2)/2
= (n^2+3*n+2)/2
= (n+1)*(n+2)/2
= ( (n+1) )* ( (n+1) + 1 ) / 2

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

It's not, it is just missing a base case.

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

### Re: Mathematical Induction - Introductory Question

Demki wrote:It's not, it is just written differently, and is missing a base case.

OK. I have some vague notion that, in solving the original question, I don't want the left-hand side to look the same as the right-hand side. Instead, I want to manipulate the right-hand side to look like something else. Is that right?

Demki
Posts: 199
Joined: Fri Nov 30, 2012 9:29 pm UTC

### Re: Mathematical Induction - Introductory Question

Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.

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

### Re: Mathematical Induction - Introductory Question

Demki wrote:Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.

Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

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

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:
Demki wrote:Yes, basically. What you want is simply to derive the (n=k+1) case given the (n=k) case, as has been done in the proof you've given, along with a base case.

Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

You start with the statement with a k in the place of the relevant variable (usually n), then, through applying a series of mathematically valid transformations (like algebra or logic), you end up with the statement with k+1 in the place of the variable. (I tried to convey this in the diagrams too)
Your derivation is correct if the transformations are correct.

ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Mathematical Induction - Introductory Question

MathDoofus wrote:Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

left_side(k) = right_side(k)
You know this is true for at least one k. (That was your first step.)

Now write
left_side(k+1) =? right_side(k+1)
You don't know this is true yet. The object is to get this to look like what you started with. Bit by bit you get the left side to look like it's earlier form, while doing exactly the same thing to the right side (to maintain the supposed equality). When simplified, the right side should comply also, and you'll be there.

If you do correct algebra, and you mange to get your first equation back, you've done it.

Hint: The second-to-last stage will probably look something like
left_side(k) + 1 =? right_side(k) + 1
and subtracting 1 from both sides gets you home. What it actually looks like depends on the equations involved.

Then, you can replace the =? in that last step with = (because you know the last step is true).... and working backwards you know the previous steps must have also been true. You end up replacing =? with = in the beginning, and add a Latin TLA at the end.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Mathematical Induction - Introductory Question

If you find function notation to be beyond your grasp, it's a good bet you don't really understand how substitution actually works, which seems to be evident from your posts in this thread. In that case, you are naturally going to have a tough time understanding what "the k+1 case" even means.

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

### Re: Mathematical Induction - Introductory Question

Eebster the Great wrote:If you find function notation to be beyond your grasp, it's a good bet you don't really understand how substitution actually works, which seems to be evident from your posts in this thread. In that case, you are naturally going to have a tough time understanding what "the k+1 case" even means.

Thanks. Always helps to have someone pile on to point out my ignorance, which I've confessed many times in this thread. The point of this thread is so that I can work out each step. Thank you to those who've tried to help with that.

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

### Re: Mathematical Induction - Introductory Question

ucim wrote:
MathDoofus wrote:Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

left_side(k) = right_side(k)
You know this is true for at least one k. (That was your first step.)

Now write
left_side(k+1) =? right_side(k+1)
You don't know this is true yet. The object is to get this to look like what you started with. Bit by bit you get the left side to look like it's earlier form, while doing exactly the same thing to the right side (to maintain the supposed equality). When simplified, the right side should comply also, and you'll be there.

If you do correct algebra, and you mange to get your first equation back, you've done it.

Hint: The second-to-last stage will probably look something like
left_side(k) + 1 =? right_side(k) + 1
and subtracting 1 from both sides gets you home. What it actually looks like depends on the equations involved.

Then, you can replace the =? in that last step with = (because you know the last step is true).... and working backwards you know the previous steps must have also been true. You end up replacing =? with = in the beginning, and add a Latin TLA at the end.

Jose

I have come back to this over the holidays, and I'm happy to report that some of everyone's advice has sunk in. Below is my understanding of the example problem.

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

First, I'll try a base case to be sure that it works for some n. I'll use 1 as the base case because it seems to be the simplest.

Base case checks out: 1 = [1(1 + 1)/2

1 = [1(2)]/2
1= 2/2
1 = 1

Next, I'll assume that the k case is true.

The k case looks like this: P(k): 1 + 2 + 3 + ... + k = [k(k + 1)]/2

And I'll use the conditional (i.e., if x, then y) to see if the (k + 1) case is true if the k case is true. To do that, I'll replace all references to k on the right-hand side with (k + 1).

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

The insight is that, because I'm using a conditional, I can replace much of the stuff on the left-hand side with the right-hand side of the k case.

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

My next goal is to try to make the left-hand side identical to the right-hand side. Although my algebra knowledge is incomplete and rusty, here's what I've come up with (I do remember the FOIL rule).

[k(k + 1)]/2 + [2(k + 1)]/2 = [(k + 1)(k + 2)]/2 ***I've given everything a common denominator***

[k(k + 1) + 2(k + 1)]/2 = [(k + 1)(k + 2)/2] ***I've simplified on the left-hand side***

(k^2 + k + 2k + 2)/2 = [(k + 1)(k + 2)]/2 ***Continuing to work on the left-hand side***

(k^2 + 3k + 2)/2 = [(k + 1)(k +2)]/2 ***Continuing to work on the left-hand side***

(k^2 + 3k + 2)/2 = (k^2 + 2k + k + 2)/2 ***Applied FOIL to the right-hand side***

(k^2 + 3k + 2)/2 = (k^2 + 3k + 2)/2 ***Left-hand side and right-hand side are now identical, so I've shown that if the k case is true, then the (k + 1) case is true. And because I've already checked a base case (and because of the well-ordering principle), I've shown that it's true for all values of n.

Is the above correct?

ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Mathematical Induction - Introductory Question

Yes, that is entirely correct (although I would have multiplied both sides by 2 to get rid of that messy fraction at my first opportunity!)

Great going!

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

cyanyoshi
Posts: 412
Joined: Thu Sep 23, 2010 3:30 am UTC

### Re: Mathematical Induction - Introductory Question

That's close to being a valid proof, but there is one bit that's not quite kosher. You showed that the formula works for the base case k=1. At this point, you wanted to show that if the formula holds for some positive integer k, then it holds for k+1 as well.
MathDoofus wrote:And I'll use the conditional (i.e., if x, then y) to see if the (k + 1) case is true if the k case is true. To do that, I'll replace all references to k on the right-hand side with (k + 1).

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

At this step, it would be better to just start with the left hand side 1+...+k+(k+1) and see if you could massage it into the expression you really want. You shouldn't logically assume that the answer you are looking for is correct for k+1 at this point. It's fine in this example because all your steps are reversable, but you could accidentally multiply both sides by zero and erroneously conclude that the induction formula is valid, when it actually isn't.

ucim
Posts: 6859
Joined: Fri Sep 28, 2012 3:23 pm UTC

### Re: Mathematical Induction - Introductory Question

Good point cyanyoshi.

Jose
Order of the Sillies, Honoris Causam - bestowed by charlie_grumbles on NP 859 * OTTscar winner: Wordsmith - bestowed by yappobiscuts and the OTT on NP 1832 * Ecclesiastical Calendar of the Order of the Holy Contradiction * Heartfelt thanks from addams and from me - you really made a difference.

Eebster the Great
Posts: 3460
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

### Re: Mathematical Induction - Introductory Question

The point about multiplying by zero is good. You could also prove that -1 is equal to +1 by squaring both sides of the following (erroneous) equation . . .

-1 = 1
(-1)^2 = 1^2
1 = 1

. . . and then concluding that because the last equation is true, the first one must also be true.

Instead, working on just one side and reaching the other for your example would look like this:

1. 1 + 2 + 3 + ... + k + (k+1) =
2. (1 + 2 + 3 + ... + k) + (k+1) =
3. k(k+1)/2 + (k+1) =
4. k(k+1)/2 + 2(k+1)/2 =
5. [k(k+1)+2(k+1)]/2 =
6. (k+1)(k+2)/2 =
7. (k+1)((k+1)+1)/2.

In step 6, I factored the numerator, since you can see k+1 is a common factor. This is logically equivalent to what you did, which was distribute both sides of the equation and show that they are equal that way. Factoring is just the reverse of FOILing, after all. That's why your proof actually works anyway, since all steps are reversible, so your proof can be turned into a proof like this. I would argue therefore that your proof is technically valid.