Math induction

[Nikitin]

Homework Statement

Prove by induction that a polygon with n angles has M_n = (n-3)n/2 diagonals.

Homework Equations

We assume that the formula M_n+1=M_n +n - 1 is correct.

The Attempt at a Solution

First of all I checked if the 1st formula is correct for n=3 (a triangle): (3-3)*3/2=0. Correct.

Second, I set M_n+1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2. This is what I'm supposed to get if I use formula number 2.

This is what I got: M_n+1=M_n +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2

So basically I finished the proof.. But problem is I don't understand what I did. I understand the concept of induction, but I don't know how I went through http://simple.wikipedia.org/wiki/Mathematical_induction" [Broken]:

3. Assume that for some value n, the statement is true. This is called the induction step.
4. Show that the statement is true for the next value, n+1.

Also please note that I have trouble understanding how to do step 3 and 4 in general, not just with this problem.

 

[Nikitin]

I mean, how did using formula number 2 help prove anything?

 

[Mark44]

Homework Statement

Prove by induction that a polygon with n angles has M_n = (n-3)n/2 diagonals.

Homework Equations

We assume that the formula M_n+1=M_n +n - 1 is correct.

No, this isn't right. For your induction hypothesis, assume that for a polygon with k angles, there are M_k= (k - 3)*(k/2) diagonals.

Now consider a polygon with (k + 1) angles. Use the induction hypothesis to show that this polygon will have M_{k + 1}= (k - 2)*(k + 1)/2 diagonals.

You should also state what M_n means. You didn't include that information.

The Attempt at a Solution

First of all I checked if the 1st formula is correct for n=3 (a triangle): (3-3)*3/2=0. Correct.

Second, I set M_n+1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2. This is what I'm supposed to get if I use formula number 2.

This is what I got: M_n+1=M_n +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2

So basically I finished the proof.. But problem is I don't understand what I did. I understand the concept of induction, but I don't know how I went through http://simple.wikipedia.org/wiki/Mathematical_induction" [Broken]:


Also please note that I have trouble understanding how to do step 3 and 4 in general, not just with this problem.

 

[Nikitin]

Mn= number of diagonals of a polygon with n angles. So M₄=2. i already did as you said, and the 2nd formula is correct according to the textbook

 

[Mark44]

Can you show me what you did? What you have in your first post isn't correct, as I pointed out.

 

[Nikitin]

I'm 99% sure that the 2nd formula is correct because the textbook says so.

can you pls tell me what I have done wrong exactly? just read over my op please and try to point out my mistakes

First of all I checked if the 1st formula is correct for n=3 (a triangle): (3-3)*3/2=0. Correct.

Second, I set M_n+1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2. This is what I'm supposed to get if I use formula number 2.

This is what I got [using formula number 2]: M_n+1=M_n +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2

So basically I finished the proof.. But problem is I don't understand what I did. I understand the concept of induction, but I don't know how I went through http://simple.wikipedia.org/wiki/Mathematical_induction" [Broken]:

3. Assume that for some value n, the statement is true. This is called the induction step.
4. Show that the statement is true for the next value, n+1.

Also please note that I have trouble understanding how to do step 3 and 4 in general, not just with this problem.

 

[Mark44]

As I said before, you are not doing this correctly. The three parts of an induction proof are:
1) Establishing that the statement holds for a base case. Typically this is k = 1, but you did it for k = 4, and this is find.
2) Assuming that the statement is true for n = k. In your case, this means that you are assuming that M_k = (k - 3) * k/2. You cannot set M_k+1 to any particular value. This is what you are doing, and why I have twice said that you aren't doing this problem correctly.
3) Use your assumption of part 2 above to show that M_k+1 = (k - 2) * (k + 1)/2. Again, you cannot start off by saying this is true. You have to show it.

You can use the fact that for a polygon with n sides, if you add one more side, there will be (n - 1) more new diagonals.

 

[Nikitin]

Hmm but I did show that, I put n+1 into n in the first M_n formula. I got what you wanted, M_n+1=(n²-n-2)/2=(n-2)(n+1)/2. Only difference between your and mine formula is that you use "k" instead of "n".

Sorry, it must have been my poor wording (English isn't my native language).




As for the second formula, a polygonal has M_n+1 = M_n +n-1 diagonals.

For a square: it's M₃₊₁=M₃+3-1 = 0+3-1=2.
For a pentagram: M₄₊₁ = M₄ +4-1 =2+4-1=5.

I used the second formula in the proof, if I substituted M_n in the second formula with M_n from the first I would get an expression for M_n+1 which equalled (n-2)(n+1)/2

 

[Mark44]

Hmm but I did show that, I put n+1 into n in the first M_n formula.

No, that's not what you do. If you just replace n by n + 1, you aren't showing anything.

I got what you wanted, M_n+1=(n²-n-2)/2=(n-2)(n+1)/2. Only difference between your and mine formula is that you use "k" instead of "n".

Sorry, it must have been my poor wording (English isn't my native language).




As for the second formula, a polygonal has M_n+1 = M_n +n-1 diagonals.

For a square: it's M₃₊₁=M₃+3-1 = 0+3-1=2.
For a pentagram: M₄₊₁ = M₄ +4-1 =2+4-1=5.

Yes, this is fine. My reasoning was flawed because I wasn't counting a diagonal that I should have counted. I have edited my original post to reflect this.

I used the second formula in the proof, if I substituted M_n in the second formula with M_n from the first I would get an expression for M_n+1 which equalled (n-2)(n+1)/2

 

[Nikitin]

Argh it must be the English, because I am 100% positive that I did it.

I'll do it again to satisfy you:
M_k+1 = (-3 + (k+1))*(k+1)/2=(k-2)*(k+1)/2. I replaced n with k+1. Previously I replaced n with n+1 on both sides of the expression. This is what I'm supposed to get when I would use the second formula to "prove" it.

There, but this really really isn't the problem, it isn't actually my proof, it's just a step.. I use the second formula for the real proof.

 

[Nikitin]

There, but this really really isn't the problem, it isn't actually my proof, it's just a step.. I use the second formula for the real proof.

To explain this closer,you know the second formula? M_n+1=M_n+n-1?

This is the next value after n, I need to show that the first formula (ie: M_n=(n-3)*n/2)) is true about n+1.




So, I know M_n from the first formula (M_n=(n-3)*n/2), so I just put it into the 2nd formula. I get M_n+1= [(n-3)*n/2] +n-1 = (n-2)*(n+1)/2

Which is what I'm supposed to get (

M_k+1 = (-3 + (k+1))*(k+1)/2=(k-2)*(k+1)/2

). So I guess if we assume that the second formula is 100% correct then the first one also must be correct and true.. Right?

 

[Mark44]

Argh it must be the English, because I am 100% positive that I did it.

I'll do it again to satisfy you:
M_k+1 = (-3 + (k+1))*(k+1)/2

How did you get the right side? I don't see where you are using the induction hypothesis; i.e., that M_k = (k - 3)*(k/2).

It looks like you are just replacing k by k + 1, and that is NOT THE WAY TO PROVE IT! You have to incorporate M_k into your proof.

=(k-2)*(k+1)/2. I replaced n with k+1. Previously I replaced n with n+1 on both sides of the expression. This is what I'm supposed to get when I would use the second formula to "prove" it.

There, but this really really isn't the problem, it isn't actually my proof, it's just a step.. I use the second formula for the real proof.

 

[Nikitin]

Yes but it isn't the actual proof, it's just a step I needed to do. It's part of the proof. See post #11.

Sorry, I misunderstood what you meant with the term "show".

 

[Deveno]

how you phrase an induction proof is kinda important.

what you need to do is this:

"Second, using the recursion formula:

M_n+1 = M_n + n - 1, we have

M_n+1 = (n-3)n/2 + n - 1, by our induction hypothesis."

now you proceed to show that the right-hand side is equal to the formula you're trying to prove for n+1:

((n+1)-3)(n+1)/2

(using k's instead of n isn't strictly necessary, but it helps keep straight what you're thinking of as a "particular value" and an "arbitrary value").

you actually did the work necessary to do a proof by induction, but you listed the steps you took in the wrong order, putting the conclusion before the proof.

 

[Nikitin]

how you phrase an induction proof is kinda important.

what you need to do is this:

"Second, using the recursion formula:

M_n+1 = M_n + n - 1, we have

M_n+1 = (n-3)n/2 + n - 1, by our induction hypothesis."

now you proceed to show that the right-hand side is equal to the formula you're trying to prove for n+1:

((n+1)-3)(n+1)/2

(using k's instead of n isn't strictly necessary, but it helps keep straight what you're thinking of as a "particular value" and an "arbitrary value").

you actually did the work necessary to do a proof by induction, but you listed the steps you took in the wrong order, putting the conclusion before the proof.

Yes, but this is actually what I was asking in OP.. Why is the claim proven just because of this operation? I don't completely understand it. Why is the formula true for n+1 just after this operation? I'm a bit foggy about this as induction proof is completely new to me.

Also I don't know what induction hypothesis even is.. It's the proof-plan, right?`

 

[Ibix]

The point is that you need to relate your (correct) maths to the behaviour of the system under study.

If you have a k-sided polygon, and you insert an extra point, how many extra diagonals do you get? Are any existing diagonals invalidated? Calculate the net change, and call this D.

Then, you just need to show that $M_k+D$ can be rearranged to look like $M_{k+1}$ and that $M_k$ is actually the correct number of diagonals for a particular k. You've already done the latter step.

 

[Deveno]

this is how an induction proof works:

say we want to prove "something" (which to simplfy things we'll call "property P") is true for all natural numbers (here, i am taking the natural numbers to start with 1. other conventions exist, be aware of this).

again, just for notation, i'll write P(k) to mean: the natural number k has property P.

now, 1 is a natural number, so if P is true for ALL natural numbers, it has to be true for 1 in particular.

so we require P(1), to start off with.

now...IF (and this is a BIG if), P true for one number meant P was also true for the next number, then:

P(1) --> P(2)
P(2) --> P(3)
P(3) --> P(4), you get the picture?

so for any natural number, like n for instance, we have the chain of implication:

P(1) --> P(2) --> P(3) -->...--> P(n-1) --> P(n).

so IF P(k) --> P(k+1) (k is some natural number, k+1 is the next natural number), AND P(1) as well, we can conclude that "eventually" (in a finite number of steps) we could prove P(n), no matter which natural number n is, which means P(n) is true for ANY natural number n.

now, sometimes a formula doesn't make sense for the first several natural numbers. but we can adapt our approach to just starting with a,
and using P(k+a)-->P(k+1+a) = P((k+a)+1)), to prove it is true for all natural numbers a+k.

(in this case, a = 2, so our "base case" is P(1+2) = P(3)).

the trick is, we somehow have to prove that there is some relationship between P(k) and P(k+1). in this problem, that relationship is given by the recursion formula:

M_n+1 = M_n + n - 1

(which certainly works for n = k).

in this problem P is:

P(n) = a polygon with n angles has M_n = (n-3)n/2 diagonals, or more briefly:

M_n = (n-3)n/2 (note this formula doesn't depend on prior calculations of M_anything).

so to prove P(k) --> P(k+1), we have to show that:

M_k+1 = ((k+1) - 3)(k+1)/2 USING the fact that M_k+1 = M_k + k - 1, AND the assumption (not yet proven) that M_k = (k-3)k/2.

obviously the formula works for 3: M₃ = (0)(3)/2 = 0, there aren't any such diagonals for a triangle.

 

[Nikitin]

The point is that you need to relate your (correct) maths to the behaviour of the system under study.

If you have a k-sided polygon, and you insert an extra point, how many extra diagonals do you get? Are any existing diagonals invalidated? Calculate the net change, and call this D.

Then, you just need to show that $M_k+D$ can be rearranged to look like $M_{k+1}$ and that $M_k$ is actually the correct number of diagonals for a particular k. You've already done the latter step.

Well, I did exactly that.. D=n-1.

 

[Nikitin]

so to prove P(k) --> P(k+1), we have to show that:

M_k+1 = ((k+1) - 3)(k+1)/2 USING the fact that M_k+1 = M_k + k - 1, AND the assumption (not yet proven) that M_k = (k-3)k/2.

This is where I have the trouble. WHY is the claim proven by such an act? I don't 100% understand just this.

 

[Mark44]

The point is that you need to relate your (correct) maths to the behaviour of the system under study.

If you have a k-sided polygon, and you insert an extra point, how many extra diagonals do you get? Are any existing diagonals invalidated? Calculate the net change, and call this D.

Then, you just need to show that $M_k+D$ can be rearranged to look like $M_{k+1}$ and that $M_k$ is actually the correct number of diagonals for a particular k. You've already done the latter step.

I disagree that what needs to be done is "rearrange" M_k + D to look like M_k+1. I might be misinterpreting what you mean by "rearrange" here, but my problem with nikotin's work is that it seems like all he is doing is replacing n by n + 1 in the formula, which is not how an induction proof is proved. If that's not what he's doing, then his work needs to be clearer.

Well, I did exactly that.. D=n-1.

 

[Deveno]

no, that's not quite what you did. let's look at your original post in detail, and i'll try to point out what went wrong.

Homework Statement

Prove by induction that a polygon with n angles has M_n = (n-3)n/2 diagonals.

Homework Equations

We assume that the formula M_n+1=M_n +n - 1 is correct.

The Attempt at a Solution

First of all I checked if the 1st formula is correct for n=3 (a triangle): (3-3)*3/2=0. Correct.

you're fine up to here.

Second, I set M_n+1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2. This is what I'm supposed to get if I use formula number 2.

this step is "out of order". it's true it's what you're "supposed to get", but you can't claim it's true just yet, you haven't proven it.

This is what I got: M_n+1=M_n +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n²-n-2)/2

this is the part that should come next. and you need to amplify it. like so:

1.)M_n+1=M_n + n - 1 (given)
2.)M_n + n - 1 = ((n-3)n/2) + n - 1 (red parts are by our induction hypothesis, the "P(n) part")

now, you haven't finished this yet, you need to do so more algebra, here.

3.)((n-3)n/2) + n - 1 = (n²-n-2)/2 (a little condensed, but OK)
4.)(n²-n-2)/2 = ((n+1)-3)(n+1)/2 (also a bit condensed, showing a bit more work here would be a good idea)

which is the desired formula (the "P(n+1)"), so you're done.

So basically I finished the proof.. But problem is I don't understand what I did. I understand the concept of induction, but I don't know how I went through http://simple.wikipedia.org/wiki/Mathematical_induction" [Broken]:


Also please note that I have trouble understanding how to do step 3 and 4 in general, not just with this problem.

your proof is actually correct, you just shouldn't have included any of the part in blue.

 

[Mark44]

so to prove P(k) --> P(k+1), we have to show that:

M_k+1 = ((k+1) - 3)(k+1)/2 USING the fact that M_k+1 = M_k + k - 1, AND the assumption (not yet proven) that M_k = (k-3)k/2.

obviously the formula works for 3: M₃ = (0)(3)/2 = 0, there aren't any such diagonals for a triangle.

This is where I have the trouble.

And it is this trouble that I've been pointing out.

WHY is the claim proven by such an act? I don't 100% understand just this.

In all induction proofs you have a sequence of statements: P₁, P₂, P₃, ..., P_n, P_n+1, ...

IF a statement at the beginning is true AND the (n + 1)st statement is true when the nth statement is true, then you can work all the way back to your base case. A common analogy for induction proofs is of a string of dominoes that are placed close together and are set upright. If we know that the (n + 1)st domino will fall when the n-th domino falls against it, and we know that the domino at the beginning will fall, then all of the dominoes will go down sequentially.

 

[Nikitin]

this step is "out of order". it's true it's what you're "supposed to get", but you can't claim it's true just yet, you haven't proven it.

No, but this is what I'm supposed to get.. To check if the formula is true, right?

this is the part that should come next. and you need to amplify it. like so:

1.)M_n+1=M_n + n - 1 (given)
2.)M_n + n - 1 = ((n-3)n/2) + n - 1 (red parts are by our induction hypothesis, the "P(n) part")

Induction hypothesis? I don't fully understand what you mean with this. I just put one expression into another.

3.)((n-3)n/2) + n - 1 = (n²-n-2)/2 (a little condensed, but OK)
4.)(n²-n-2)/2 = ((n+1)-3)(n+1)/2 (also a bit condensed, showing a bit more work here would be a good idea)

which is the desired formula (the "P(n+1)"), so you're done.

Does 3.) mean what I'm supposed to get? Like, the goal?
Does 4.) mean the final result, the goal itself?

In all induction proofs you have a sequence of statements: P1, P2, P3, ..., Pn, Pn+1, ...

IF a statement at the beginning is true AND the (n + 1)st statement is true when the nth statement is true, then you can work all the way back to your base case. A common analogy for induction proofs is of a string of dominoes that are placed close together and are set upright. If we know that the (n + 1)st domino will fall when the n-th domino falls against it, and we know that the domino at the beginning will fall, then all of the dominoes will go down sequentially.

yes, I kind of understand that, it's actually pushing the first domino down that I'm struggling with.

 

[Deveno]

This is where I have the trouble. WHY is the claim proven by such an act? I don't 100% understand just this.

it has to do with how natural numbers are defined.

natural numbers have a "base number" (1).

if k is a natural number, so is k+1 (we get all the natural numbers by "counting up by one"),

natural numbers are "defined inductively", so induction works for them.

think about this a little bit: what is 2, really?

it's: "1 and 1".

similarly, 3 is "1 and 1 and 1" (it's simpler to type 1+1+1, right?).

what we MEAN, when we say "k is a natural number" is:

k = 1+1+1+...+1 (for a certain number of 1's, namely, "k").

k is just short-hand for writing 1+1+...+1 (k times), because face it, such a notation would be really awkward, and hard to use.

so, if "going up by 1" doesn't change the truth of P (P(k+1) is true whenever P(k) is), and P(1) is true, then we know:

P(1+1) is true
P(1+1+1) is true
P(1+1+1+1) is true...

then P(k) must be true, too (since k is just 1 added k times).

 

[Nikitin]

it has to do with how natural numbers are defined.

natural numbers have a "base number" (1).

if k is a natural number, so is k+1 (we get all the natural numbers by "counting up by one"),

natural numbers are "defined inductively", so induction works for them.

think about this a little bit: what is 2, really?

it's: "1 and 1".

similarly, 3 is "1 and 1 and 1" (it's simpler to type 1+1+1, right?).

what we MEAN, when we say "k is a natural number" is:

k = 1+1+1+...+1 (for a certain number of 1's, namely, "k").

k is just short-hand for writing 1+1+...+1 (k times), because face it, such a notation would be really awkward, and hard to use.

so, if "going up by 1" doesn't change the truth of P (P(k+1) is true whenever P(k) is), and P(1) is true, then we know:

P(1+1) is true
P(1+1+1) is true
P(1+1+1+1) is true...

then P(k) must be true, too (since k is just 1 added k times).

Nono, I mean why does doing this operation

so to prove P(k) --> P(k+1), we have to show that:

M_k+1 = ((k+1) - 3)(k+1)/2 USING the fact that M_k+1 = M_k + k - 1, AND the assumption (not yet proven) that M_k = (k-3)k/2.

prove that the original expression is valid for n+1 (and thus for all other natural numbers)? I understand the "domino effect", it's actually the trigger I don't fully understand. I can do an induction proof, but I don't understand it.

Maybe I just need to sleep on this...

 

[Deveno]

no, it's fine, you're doing great.

in this particular example, we had a "free gift" to start out with:

M_n+1 = M_n + n - 1.

that gives us a link between:

some formula in n, and some formula in (n+1).

in a sense, the formula above, gives us "leverage" to help prove "the other formula":

M_n = (n-3)n/2.

now, i admit the word "formula" is doing some double-duty, here. but that often happens in inductive proofs. look at it this way:

M_n+1 = M_n + n - 1 is really a "an alternate definition" of "the number of diagonals of an n-gon". but this definition is unwieldy to use: if we wanted to calculate M₁₀₀₀, we'd have to calculate 999 other things first.

so the "strategy" is to use M_n+1 = M_n + n - 1 to prove a closed formula for M_n (one that only depends on n).

why does induction work? it seems like magic, honestly. it's almost like we prove what we want to prove, by assuming what we want to prove is true. but that misses the key point:

the key point is NOT "assume P(k) is true", it's "IF P(k) THEN P(k+1)". that will cause a chain reaction...IF...our base case can spark it off.

 

[Mark44]

the key point is NOT "assume P(k) is true", it's "IF P(k) THEN P(k+1)".

With "IF P(k) THEN P(k+1)" you are assuming that P(k) is true, so I'm not sure what your point is here.

that will cause a chain reaction...IF...our base case can spark it off.

 

[Deveno]

With "IF P(k) THEN P(k+1)" you are assuming that P(k) is true, so I'm not sure what your point is here.

my point is that it is not the "if" that matters, it's the "if" and the "then" (they come in a linked pair).

often, when students struggle with induction, they think:

"how can we just assume the induction hypothesis is true"?

and you can't, you don't know it's true.

but we're not considering the assumption in a vacuum, we're considering an assumption/conclusion pair.

yes, "if p" is a part of "if p then q", but their truth-values aren't even close to being the same.

 

[Nikitin]

hmm so it's nothing more special than using another formula, which we know is 100% true, for the proof.

Anyways guys, thanks allot for your time and patience, I really appreciate it. good night

 

[Mark44]

my point is that it is not the "if" that matters, it's the "if" and the "then" (they come in a linked pair).

Gotcha. I thought that might be what you meant.

often, when students struggle with induction, they think:

"how can we just assume the induction hypothesis is true"?

and you can't, you don't know it's true.

but we're not considering the assumption in a vacuum, we're considering an assumption/conclusion pair.

yes, "if p" is a part of "if p then q", but their truth-values aren't even close to being the same.

 

[Ibix]

I disagree that what needs to be done is "rearrange" M_k + D to look like M_k+1. I might be misinterpreting what you mean by "rearrange" here, but my problem with nikotin's work is that it seems like all he is doing is replacing n by n + 1 in the formula, which is not how an induction proof is proved. If that's not what he's doing, then his work needs to be clearer.

I was getting at what you were getting at: that if you know how to transform the number of diagonals for a k-gon into that for a (k+1)-gon, and if that transform maps the proposed number of diagonals for a k-gon to the proposed number of diagonals for a (k+1)-gon then the inductive hypothesis is satisfied. All that remains to be done is to confirm that the proposed number of diagonals is correct for one case.

OP: I sometimes find a counter-example helpful. I propose that the number of diagonals is much simpler: M'_n=n. The inductive hypothesis would have it that if this is true for some n=k then M'_k+1 (=k+1) should be equal to M'_k+k-1 (=2k-1). Since this statement is not true, my idea is not consistent with the inductive hypothesis and so fails.

Try again: M''_n=M_n+3. This does satisfy the inductive hypothesis (easy to verify since I've stolen the correct solution and broken it). So, if it were true for some n=k, then it would be true for all n. However, it is not true for a concrete value of n, say n=3, so fails.