# Math induction

## Homework Statement

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

## Homework Equations

We assume that the formula Mn+1=Mn +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 Mn+1 = ((n+1)-3)(n+1)/2 = (n2-n-2)/2. This is what I'm supposed to get if I use formula number 2.

This is what I got: Mn+1=Mn +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n2-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.

Last edited by a moderator:

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

Mark44
Mentor

## Homework Statement

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

## Homework Equations

We assume that the formula Mn+1=Mn +n - 1 is correct.
No, this isn't right. For your induction hypothesis, assume that for a polygon with k angles, there are Mk= (k - 3)*(k/2) diagonals.

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

You should also state what Mn 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 Mn+1 = ((n+1)-3)(n+1)/2 = (n2-n-2)/2. This is what I'm supposed to get if I use formula number 2.

This is what I got: Mn+1=Mn +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n2-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.

Last edited by a moderator:
Mn= number of diagonals of a polygon with n angles. So M4=2. i already did as you said, and the 2nd formula is correct according to the textbook

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

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 Mn+1 = ((n+1)-3)(n+1)/2 = (n2-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]: Mn+1=Mn +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n2-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.

Last edited by a moderator:
Mark44
Mentor
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 Mk = (k - 3) * k/2. You cannot set Mk+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 Mk+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.

Last edited:
Hmm but I did show that, I put n+1 into n in the first Mn formula. I got what you wanted, Mn+1=(n2-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 Mn+1 = Mn +n-1 diagonals.

For a square: it's M3+1=M3+3-1 = 0+3-1=2.
For a pentagram: M4+1 = M4 +4-1 =2+4-1=5.

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

Last edited:
Mark44
Mentor
Hmm but I did show that, I put n+1 into n in the first Mn 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, Mn+1=(n2-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 Mn+1 = Mn +n-1 diagonals.

For a square: it's M3+1=M3+3-1 = 0+3-1=2.
For a pentagram: M4+1 = M4 +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 Mn in the second formula with Mn from the first I would get an expression for Mn+1 which equalled (n-2)(n+1)/2

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

I'll do it again to satisfy you:
Mk+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.

Last edited:
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? Mn+1=Mn+n-1?

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

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

Which is what I'm supposed to get (
Mk+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?

Last edited:
Mark44
Mentor
Argh it must be the English, because I am 100% positive that I did it.

I'll do it again to satisfy you:
Mk+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 Mk = (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 Mk 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.

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:

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

Mn+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.

how you phrase an induction proof is kinda important.

what you need to do is this:

"Second, using the recursion formula:

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

Mn+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.

Last edited:
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:

Mn+1 = Mn + n - 1

(which certainly works for n = k).

in this problem P is:

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

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

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

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

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

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.

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

Mk+1 = ((k+1) - 3)(k+1)/2 USING the fact that Mk+1 = Mk + k - 1, AND the assumption (not yet proven) that Mk = (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
Mentor
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" Mk + D to look like Mk+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 Mn = (n-3)n/2 diagonals.

## Homework Equations

We assume that the formula Mn+1=Mn +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 Mn+1 = ((n+1)-3)(n+1)/2 = (n2-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: Mn+1=Mn +n - 1 = ((n-3)n/2) +n - 1 = ((n+1)-3)(n+1)/2 = (n2-n-2)/2

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

1.)Mn+1=Mn + n - 1 (given)
2.)Mn + 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 = (n2-n-2)/2 (a little condensed, but OK)
4.)(n2-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.

Last edited by a moderator:
Mark44
Mentor
so to prove P(k) --> P(k+1), we have to show that:

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

obviously the formula works for 3: M3 = (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: 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.

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.)Mn+1=Mn + n - 1 (given)
2.)Mn + 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 = (n2-n-2)/2 (a little condensed, but OK)
4.)(n2-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.

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

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.

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:

Mk+1 = ((k+1) - 3)(k+1)/2 USING the fact that Mk+1 = Mk + k - 1, AND the assumption (not yet proven) that Mk = (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...

Last edited:
Deveno
no, it's fine, you're doing great.

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

Mn+1 = Mn + 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":

Mn = (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:

Mn+1 = Mn + 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 M1000, we'd have to calculate 999 other things first.

so the "strategy" is to use Mn+1 = Mn + n - 1 to prove a closed formula for Mn (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
Mentor
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.

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
Mentor
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.