The question is "Determine the number of diagonals (that do not intersect) necessary to divide a convex polygon of n sides into triangles."
I am having problems approaching this question can any one give me some ideas of how approaching these types of question any help will be appreciated
The proof by induction would start with the base case, a triangle, for which the answer is 0, as it is a triangle itself. So for n=3, diagonals=0. Now take a four-sided poligon and from one of its vertex, say A, draw a diagonal. By doing this we get 2 triangles, so the answer for n=4 is d=1. Now add one side to the polygon, a new vertex will be added as well, and we can match our vertex A with this new vertex obtaining a new triangle. So the answer for n=4+1 is d=1+1 By induction, for n=k, d=(k-4)+= k-3
So the answer is n-3
Hint: A little experimentation leads to the conjecture we can do it using $n-3$ diagonals.
For the induction step, suppose this is true for a convex polygon with $k$ sides. To deal with the case $k+1$, let $P,Q,R$ be consecutive vertices, and join $PR$. That divides our polygon into a triangle and a convex polygon with $k$ sides. Apply the induction hypothesis to this polygon.
Added: The phrasing "are needed" suggests that we also should prove that we cannot do it with fewer than $n-3$ lines. For that, strong induction is the right tool.
In the case $n=3$, we certainly need at least $n-3$ diagonals. Suppose that at least $n-3$ diagonals are needed for all convex $k$-gons with $k\lt n$. We show at least $n-3$ diagonals are needed for a convex $n$-gon.
So take a a division of the polygon into triangles by non-intersecting diagonals. Let $\ell$ be one of the diagonals of this division. This divides our $n$-gon into a $p$-gon and a $q$-gon, where $p+q=n+2$. By the induction hypothesis, at least $p-3$ diagonals are needed for the $p$-gon, and at least $q-3$ for the $q$-gon. This gives (including $\ell$) a total of at least $(p-3)+(q-3)+1=(p+q)-5=(n+2)-5=n-3$ diagonals.
