# Mathematical Proof By Induction

Watch this threadPage 1 of 1

Go to first unread

Skip to page:

Ihatescales

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#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

Questions - https://imgur.com/gallery/FgctocR

0

reply

Ajmaster

Badges:
6

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2

Ajmaster

Badges:
6

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3

Report

#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

reply

Ihatescales

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4

(Original post by

I can- you are doing further maths arent you?

**Ajmaster**)I can- you are doing further maths arent you?

0

reply

RDKGames

Badges:
20

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5

Report

#5

(Original post by

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

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

0

reply

Ihatescales

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6

(Original post by

What are the definitions of a simple polygon and triangulation which you received?

**RDKGames**)What are the definitions of a simple polygon and triangulation which you received?

0

reply

ghostwalker

Badges:
17

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7

Report

#7

(Original post by

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

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

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

reply

DFranklin

Badges:
18

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8

Report

#8

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

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

reply

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9

(Original post by

"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

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

The normal description of a simple polygon would be one where the edges don't

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?

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

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

reply

DFranklin

Badges:
18

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10

Report

#10

(Original post by

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.

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

0

reply

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11

(Original post by

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.

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

reply

DFranklin

Badges:
18

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#12

Report

#12

(Original post by

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.

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

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

reply

Badges:
10

Rep:

?
You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#13

(Original post by

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.

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.

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

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top