Let $P(n)$ be the statement that when non-intersecting diagonals are drawn inside a convex polygon with $n$ sides, at least two vertices of the polygon are not endpoints of any of these diagonals.
a) Show that when we attempt to prove $P(n)$ for all integers $n$ with $n\ge3$ using strong induction, the inductive step does not go through.
b) Show that we can prove that $P(n)$ is true for all integers $n\ge3$ by proving by strong induction the stronger assertion $Q(n)$, for $n\ge 4$ states that whenever non-intersecting diagonals are drawn inside a convex polygon with n sides, at least non-adjacent vertices are not endpoints of any of these diagonals.
My questions are:
1) How to prove P(3) since no diagonal can be drawn in it? Can we just say P(3) is true because it is a triangle by itself and there is no possible diagonal in it? I pretty doubt this justification.
2) Why the inductive step for P(n) fails? How does the Q(n) helps the case?
P.S: If possible I hope the community can draw some figures to let me understand better. I am pretty much confuse about P(3) and why inductive step fails.
I have zero clue. But I tried and the following is my answer:
Basis step: $P(3)$ is trivially true because it is a triangle by itself and there is no possible diagonal in it.
Inductive step: Suppose $P(3)$ to $P(n)$ are true, then we must show that $P(n+1)$ is also true. Consider that we divide/diagonalize the convex polygon $P$ into smaller polygons $P1$ and $P2$, then by inductive hypothesis we know that $P1$ and $P2$ has at least two vertices that are not end points of their own non-intersecting diagonals drawn inside their convex polygons. Nevertheless, these non-endpoints could be the endpoints of the diagonal of the larger polygon P. For this reason, we introduce $Q(n)$.
Basis step: $Q(4)$ is true because we can divide/diagonalize the convex polygon from a particular vertex to another non-adjacent vertex. Since there is only one non-adjacent vertex, we know that there are two vertices that are not the endpoint of the diagonals-the adjacent vertices.
Inductive Step: Suppose $Q(4)$ to $Q(n)$ are true, then we show that $Q(n+1)$ is also true. To see this, consider that we divide/diagonalize the convex polygons into two smaller polygons $P1$ and $P2$. By inductive hypothesis, we know that the two smaller polygons have at least two vertices that are not endpoints of their own convex polygons. Suppose in the worst case where there are only two vertices and one of their vertices are endpoint of the diagonal of the larger polygon $P$, then each smaller polygon has one vertices that are non endpoints. The two smaller polygons makes up at least two non-adjacent vertices.
Using Q(n), we therefore say that P(n+1) is also true. Therefore, P(n) is true for every integer $n\ge 3$
$P(3)$ is trivially true.
Task a) refers to fruitless attempts by the original poser of the problem. It's difficult to prove that some ideas wont work. I'd say that inventing a stronger inductive statement $Q(n)$ and proving it is still proving $P(n)$ by strong induction.
Here is how I'd prove the claim: Continue drawing diagonals until the given polygon is fully triangulated. Consider the graph $\Gamma$ having the barycenters $m_i$ of the triangles as vertices and for each diagonal separating two triangles an edge between their barycenters. This $\Gamma$ is a tree, hence has at least two leaves. This means that there are at least two triangles having just one diagonal as an edge.