Math induction

  • Thread starter Nikitin
  • Start date
  • #1
726
27

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:

Answers and Replies

  • #2
726
27
I mean, how did using formula number 2 help prove anything?
 
  • #3
34,687
6,393

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:
  • #4
726
27
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:
  • #5
34,687
6,393
Can you show me what you did? What you have in your first post isn't correct, as I pointed out.
 
  • #6
726
27
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:
  • #7
34,687
6,393
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:
  • #8
726
27
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:
  • #9
34,687
6,393
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
 
  • #10
726
27
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:
  • #11
726
27
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:
  • #12
34,687
6,393
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.
 
  • #13
726
27
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
Deveno
Science Advisor
906
6
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
726
27
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?`
 
  • #16
Ibix
Science Advisor
Insights Author
2020 Award
7,396
6,481
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:
  • #17
Deveno
Science Advisor
906
6
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
726
27
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.


Well, I did exactly that.. D=n-1.
 
  • #19
726
27
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.
 
  • #20
34,687
6,393
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.
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.
 
  • #21
Deveno
Science Advisor
906
6
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:
  • #22
34,687
6,393
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.
 
  • #23
726
27
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.
 
  • #24
Deveno
Science Advisor
906
6
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).
 
  • #25
726
27
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:

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:

Related Threads on Math induction

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
702
  • Last Post
Replies
4
Views
953
  • Last Post
Replies
2
Views
966
  • Last Post
Replies
12
Views
1K
  • Last Post
Replies
1
Views
860
  • Last Post
Replies
12
Views
1K
Replies
7
Views
5K
  • Last Post
Replies
9
Views
2K
Top