1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Math induction

  1. Oct 31, 2011 #1
    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. jcsd
  3. Oct 31, 2011 #2
    I mean, how did using formula number 2 help prove anything?
  4. Oct 31, 2011 #3


    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
  5. Oct 31, 2011 #4
    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
  6. Oct 31, 2011 #5


    Staff: Mentor

    Can you show me what you did? What you have in your first post isn't correct, as I pointed out.
  7. Oct 31, 2011 #6
    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
  8. Oct 31, 2011 #7


    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
  9. Oct 31, 2011 #8
    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
  10. Oct 31, 2011 #9


    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.
  11. Oct 31, 2011 #10
    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
  12. Oct 31, 2011 #11
    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
  13. Oct 31, 2011 #12


    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.
  14. Oct 31, 2011 #13
    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".
  15. Oct 31, 2011 #14


    User Avatar
    Science Advisor

    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:


    (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.
  16. Oct 31, 2011 #15
    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?`
  17. Oct 31, 2011 #16


    User Avatar
    Science Advisor

    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 [itex]M_k+D[/itex] can be rearranged to look like [itex]M_{k+1}[/itex] and that [itex]M_k[/itex] is actually the correct number of diagonals for a particular k. You've already done the latter step.
    Last edited: Oct 31, 2011
  18. Oct 31, 2011 #17


    User Avatar
    Science Advisor

    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.
  19. Oct 31, 2011 #18

    Well, I did exactly that.. D=n-1.
  20. Oct 31, 2011 #19
    This is where I have the trouble. WHY is the claim proven by such an act? I don't 100% understand just this.
  21. Oct 31, 2011 #20


    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.

  22. Oct 31, 2011 #21


    User Avatar
    Science Advisor

    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.

    you're fine up to here.

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

    your proof is actually correct, you just shouldn't have included any of the part in blue.
    Last edited by a moderator: May 5, 2017
  23. Oct 31, 2011 #22


    Staff: Mentor

    And it is this trouble that I've been pointing out.
    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.
  24. Oct 31, 2011 #23
    No, but this is what I'm supposed to get.. To check if the formula is true, right?
    Induction hypothesis? I don't fully understand what you mean with this. I just put one expression into another.
    Does 3.) mean what I'm supposed to get? Like, the goal?
    Does 4.) mean the final result, the goal itself?

    yes, I kind of understand that, it's actually pushing the first domino down that I'm struggling with.
  25. Oct 31, 2011 #24


    User Avatar
    Science Advisor

    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).
  26. Oct 31, 2011 #25
    Nono, I mean why does doing this operation
    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: Oct 31, 2011
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook