Let P(n) be the statement: Given a convex polygon with n sides, when all nonintersecting diagonals are drawn inside the polygons at least two of the vertices of the polygon are not endpoints of any diagonals.

Let Q(n) be the statement: Given a convex polygon with n sides, when all nonintersecting diagonals are drawn inside the polygons at least two nonadjacent vertices of the polygon are not endpoints of any diagonals.

One point of this problem is to see the difference introduced by the word nonadjacent in Q(n).

a) Show that when we attempt to prove P(n) for all integers n with n 3 using strong induction, the inductive step does not go through.

Note that strong induction relies on multiple preceding cases, often all the preceding cases. Weak induction relies only on the one preceding case. You should NOT try to use weak induction in either part a) or part b).

b) Show that we can prove that P(n) is true for all integers n with n 3 by proving via strong induction the stronger assertion Q(n), for n 4. Note that for part b) there are two steps. First prove Q(n), for n 4, and then prove P(n) for n 3.