Math induction

1. Oct 31, 2011

Nikitin

1. The problem statement, all variables and given/known data
Prove by induction that a polygon with n angles has Mn = (n-3)n/2 diagonals.

2. Relevant equations

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

3. 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: May 5, 2017
2. Oct 31, 2011

Nikitin

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

3. Oct 31, 2011

Staff: Mentor

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.

Last edited by a moderator: May 5, 2017
4. Oct 31, 2011

Nikitin

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: Oct 31, 2011
5. Oct 31, 2011

Staff: Mentor

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

6. Oct 31, 2011

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

Last edited by a moderator: May 5, 2017
7. Oct 31, 2011

Staff: 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: Oct 31, 2011
8. Oct 31, 2011

Nikitin

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: Oct 31, 2011
9. Oct 31, 2011

Staff: Mentor

No, that's not what you do. If you just replace n by n + 1, you aren't showing anything.
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.

10. Oct 31, 2011

Nikitin

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: Oct 31, 2011
11. Oct 31, 2011

Nikitin

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 (
). 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: Oct 31, 2011
12. Oct 31, 2011

Staff: Mentor

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.

13. Oct 31, 2011

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

14. Oct 31, 2011

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.

15. Oct 31, 2011

Nikitin

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

16. Oct 31, 2011

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: Oct 31, 2011
17. Oct 31, 2011

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.

18. Oct 31, 2011

Nikitin

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

19. Oct 31, 2011

Nikitin

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

20. Oct 31, 2011

Staff: Mentor

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.