Page 7 of 7

### Re: Mathematical Induction - Introductory Question

Posted: Wed May 03, 2017 4:39 pm UTC
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).

### Re: Mathematical Induction - Introductory Question

Posted: Wed May 03, 2017 4:42 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Wed May 03, 2017 4:45 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Wed May 03, 2017 5:11 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Sat May 06, 2017 9:45 pm UTC
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

### Re: Mathematical Induction - Introductory Question

Posted: Sat May 06, 2017 10:04 pm UTC
It's not, it is just missing a base case.

### Re: Mathematical Induction - Introductory Question

Posted: Sat May 06, 2017 10:05 pm UTC
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?

### Re: Mathematical Induction - Introductory Question

Posted: Sat May 06, 2017 10:11 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Sat May 06, 2017 10:23 pm UTC
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)?

### Re: Mathematical Induction - Introductory Question

Posted: Sun May 07, 2017 2:52 am UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Sun May 07, 2017 4:17 am UTC
MathDoofus wrote:Gotcha. How do I know when I've correctly derived the k + 1 case (the then) from the k case (the if)?

Start with
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

### Re: Mathematical Induction - Introductory Question

Posted: Sun May 07, 2017 5:14 am UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Sun May 07, 2017 12:53 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Fri Dec 29, 2017 3:40 pm UTC
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)?

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

### Re: Mathematical Induction - Introductory Question

Posted: Fri Dec 29, 2017 5:00 pm UTC
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

### Re: Mathematical Induction - Introductory Question

Posted: Fri Dec 29, 2017 5:13 pm UTC
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.

### Re: Mathematical Induction - Introductory Question

Posted: Fri Dec 29, 2017 8:11 pm UTC
Good point cyanyoshi.

Jose

### Re: Mathematical Induction - Introductory Question

Posted: Fri Dec 29, 2017 10:11 pm UTC
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.