# Mathematical Proof By Induction

#1
Hey guys, I was just wondering if anyone could possibly help/ guide me on any or all of the following questions? I feel like I’m not fully understanding the thought process behind the induction concept. Especially in question 5 & 6. Thanks anyone in advance for your time.

Questions - https://imgur.com/gallery/FgctocR
0
3 years ago
#2
I can- you are doing further maths arent you?
0
3 years ago
#3
You are going to have to first get an expression for the triangulation of a poylgon with n sides. Then check if it works for n=1 then assume that it works for n=k. Having done that it should simplify as an aswer.(This is a guess I havent worked it out or anything, just thinking this may help). After that make an expression to prove it works for n=k+1. This should mean that this expression works.
0
#4
(Original post by Ajmaster)
I can- you are doing further maths arent you?
No, I haven't done further maths, this is one of the first lecture question sheets we have been given in university. I haven't seen PBI before, so I thought I'd get in as much practice and understanding as I can.
0
3 years ago
#5
(Original post by Ihatescales)
Hey guys, I was just wondering if anyone could possibly help/ guide me on any or all of the following questions? I feel like I’m not fully understanding the thought process behind the induction concept. Especially in question 5 & 6. Thanks anyone in advance for your time.

Questions - https://imgur.com/gallery/FgctocR
What are the definitions of a simple polygon and triangulation which you received?
0
#6
(Original post by RDKGames)
What are the definitions of a simple polygon and triangulation which you received?
From the top of my head, I think a simple polygon was just a polygon whose edges don't overlap, just like a hexagon etc. Triangulation is the process of dividing something (in this case the polygon) into multiple triangles
0
3 years ago
#7
(Original post by Ihatescales)
From the top of my head, I think a simple polygon was just a polygon whose edges don't overlap, just like a hexagon etc. Triangulation is the process of dividing something (in this case the polygon) into multiple triangles
"From the top of my head" won't do. You need to find the definitions.

Here's a polygon that meets your criteria as so far stated, and no triangle has two edges in common with the external edges.

0
3 years ago
#8
(Original post by Ihatescales)
From the top of my head, I think a simple polygon was just a polygon whose edges don't overlap, just like a hexagon etc. Triangulation is the process of dividing something (in this case the polygon) into multiple triangles
The normal description of a simple polygon would be one where the edges don't intersect. (You also want to have a single closed curve - i.e. it's not just a random collection of sometimes-unconnected edges, and you don't have a polygon with holes).

Your description of triangulation is incomplete, because if you take a square and divide it into 4 triangles by the two lines forming the diagonals, you get a "triangulation" (by your definition) where no triangle has more than one edge that's on the exterior of the square (so the result you're being asked to prove would be false).

OK, now here's where the rant begins:

How can you say you need help with question 5 when you obviously haven't done your basic homework in terms of understanding the terms in the question? If you don't even understand what you're trying to prove, how do you think you have a chance of being able to solve it?
0
#9
(Original post by ghostwalker)
"From the top of my head" won't do. You need to find the definitions.

Here's a polygon that meets your criteria as so far stated, and no triangle has two edges in common with the external edges.

(Original post by DFranklin)
The normal description of a simple polygon would be one where the edges don't intersect. (You also want to have a single closed curve - i.e. it's not just a random collection of sometimes-unconnected edges, and you don't have a polygon with holes).

Your description of triangulation is incomplete, because if you take a square and divide it into 4 triangles by the two lines forming the diagonals, you get a "triangulation" (by your definition) where no triangle has more than one edge that's on the exterior of the square (so the result you're being asked to prove would be false).

OK, now here's where the rant begins:

How can you say you need help with question 5 when you obviously haven't done your basic homework in terms of understanding the terms in the question? If you don't even understand what you're trying to prove, how do you think you have a chance of being able to solve it?
I won't deny that both of your points are valid. I suppose I am trying to jump the gun here in trying to catch up where I lack in experience. So the real given definitions are as follows:

A Polygon is a closed geometric figure formed by a sequence of line segments known as sides or edges. A Polygon is simple if no two non-consecutive sides intersect.
Triangulation, then, is the process of dividing a simple Polygon into triangles by adding non-intersecting diagonals.
0
3 years ago
#10
(Original post by Ihatescales)
I won't deny that both of your points are valid. I suppose I am trying to jump the gun here in trying to catch up where I lack in experience. So the real given definitions are as follows:

A Polygon is a closed geometric figure formed by a sequence of line segments known as sides or edges. A Polygon is simple if no two non-consecutive sides intersect.
Triangulation, then, is the process of dividing a simple Polygon into triangles by adding non-intersecting diagonals.
To cut to the chase:. Q5&Q6 are *hard*. So hard that I think there's very little chance of even a very good student solving them from scratch. Either you've been given some pretty big hints in your lectures you're not telling us, or you're basically going to have to Google for proofs and try to understand them.
0
#11
(Original post by DFranklin)
To cut to the chase:. Q5&Q6 are *hard*. So hard that I think there's very little chance of even a very good student solving them from scratch. Either you've been given some pretty big hints in your lectures you're not telling us, or you're basically going to have to Google for proofs and try to understand them.
I'm pretty overwhelmed by them myself, so I didn't take all that much in (or understand much of what I did). For 5a, I think I got about as far as drawing in the first diagonal onto the polygon 'P' and then expressing the remaining two polygon as R & Q, and then understanding that the total edges of P = R + Q - 2. The minimum edges one of the polygon could take would be 3, and the max k-1 I think. I think there lies a contradiction somewhere which shows the difficulty in the strong induction but I'm not sure.

I think I'll just completely go over everything from the start I guess, I don't think I'm following the question properly. I think E(n) is definitely true, I just don't know how to apply strong induction to the scenario.
0
3 years ago
#12
(Original post by Ihatescales)
I'm pretty overwhelmed by them myself, so I didn't take all that much in (or understand much of what I did). For 5a, I think I got about as far as drawing in the first diagonal onto the polynomial 'P' and then expressing the remaining two polynomials as R & Q, and then understanding that the total edges of P = R + Q - 2. The minimum edges one of the polynomials could take would be 3, and the max k-1 I think. Whether any of this even I think there lies a contradiction somewhere which proves 5a) but I'm just not sure.

I think I'll just completely go over everything from the start I guess, I don't think I'm following the question properly. I think E(n) is definitely true, I just don't know how to apply strong induction to the scenario.
Got to be blunt here - this is pretty unintelligble; you keep saying polynomial where I assume you mean polygon, and talking about "proving 5a" is just wrong - as in "that's not even what you should be trying to do".

I'll be honest; I'm not entirely a novice at this stuff, spent a fair bit of time Googling, and it would still take me a lot of work to provide proofs for these questions I was happy with.

For Q5, my thoughts would be along the lines of "find a diagonal to cut" and divide into 2 pieces. By induction each piece has one (or two, depending on if you're talking 5a or 5b) triangles satisfying the conditions. (Oh, and I'm going to follow the literature and call such triangles "ears" from now on). If you only know each piece has 1 ear, you have the problem that if those ears lie along the join, you lose both ears and you're stuffed. If instead you know each piece has two ears, then you have 4 in total, so you can lose 2 and still be OK.

However, there's a lot of tacit assumptions in this about how joining can't possibly lose us any other ears, and you also have to worry about what happens if the diagonal you cut involves cutting off a single triangle (ear). I'm not sure how hard this is to fix, but the fact that every proof I found was a lot more complicated, even though the author clearly could easily have made an argument like mine if he wanted to, makes me worry that it is in fact hard.

For Q6: it's fairly easy to prove the inequality version. I've found a few proofs of the equality version and they are all pretty complicated and non-obvious.

The jump in difficulty between Q1-4 and Q5-6 is absolutely huge in my opinion and I'm really not sure what the lecturer's reasoning is.
0
#13
(Original post by DFranklin)
Got to be blunt here - this is pretty unintelligble; you keep saying polynomial where I assume you mean polygon, and talking about "proving 5a" is just wrong - as in "that's not even what you should be trying to do".

I'll be honest; I'm not entirely a novice at this stuff, spent a fair bit of time Googling, and it would still take me a lot of work to provide proofs for these questions I was happy with.

For Q5, my thoughts would be along the lines of "find a diagonal to cut" and divide into 2 pieces. By induction each piece has one (or two, depending on if you're talking 5a or 5b) triangles satisfying the conditions. (Oh, and I'm going to follow the literature and call such triangles "ears" from now on). If you only know each piece has 1 ear, you have the problem that if those ears lie along the join, you lose both ears and you're stuffed. If instead you know each piece has two ears, then you have 4 in total, so you can lose 2 and still be OK.

However, there's a lot of tacit assumptions in this about how joining can't possibly lose us any other ears, and you also have to worry about what happens if the diagonal you cut involves cutting off a single triangle (ear). I'm not sure how hard this is to fix, but the fact that every proof I found was a lot more complicated, even though the author clearly could easily have made an argument like mine if he wanted to, makes me worry that it is in fact hard.

For Q6: it's fairly easy to prove the inequality version. I've found a few proofs of the equality version and they are all pretty complicated and non-obvious.

The jump in difficulty between Q1-4 and Q5-6 is absolutely huge in my opinion and I'm really not sure what the lecturer's reasoning is.
Yes sorry that's what I meant, I was doing polynomial work earlier so it's just stuck in my head. I also worded that wrongly, what I meant was to search for the difficulty in the strong induction. As you said yourself I obviously don't know where to start with it (or have a good enough understanding of the topic in general) so I'll simply leave it for now until I have a better understanding of all the problems components. Thanks for the time though, I appreciate it.
0
X

new posts
Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### Poll

Join the discussion

Yes (117)
68.82%
No (34)
20%
I didn't use it to prepare (19)
11.18%