Induction: Every triangulation of an n-sided polygon has n − 2 triangles

Question

I am having trouble understanding a certain proof.

Claim: Every triangulation of an $n$-sided polygon has $n-2$ triangles.

Base Case ($n=3$): Trivial.

We let $P$ be a polygon with $n$ edges. A diagonal is drawn between two vertices of $P$, splitting $P$ up into two smaller polygons $a$ and $b$. Polygon $a$ has $k+1$ edges ($k$ edges of $P$ plus the diagonal), where $k$ is between $2$ and $n-2$. Then, polygon $b$ has $n-k+1$ edges ($n-k$ edges of $P$ plus the diagonal). If we apply the induction hypothesis to polygon $a$, then polygon $a$ can be broken up into $k-1$ triangles. Likewise, by applying the induction hypothesis to polygon $b$, polygon $b$ can be broken up into $n-k-1$ triangles. Putting polygons $a$ and $b$ together, we get $n-2$ triangles.

$(k-1)+(n-k-1) = n-2$ triangles.

I think my confusion arises when considering that we didn't use the induction hypothesis for $n+1$ sides. Instead, we used the induction hypothesis separately on two sub polygons of $P$.

Here's the proof I'm referencing: https://www.cise.ufl.edu/~ungor/courses/fall08/polytri.pdf

Answer 1

This is strong induction. Let $\Phi(n)$ be the statement that all triangulations of $n$-gons have $n-2$ triangles. Instead of the "weak" induction step $$\Phi(n)\implies \Phi(n+1),$$ we use $$\tag1 (\forall k\le n\colon \Phi(k))\implies \Phi(n+1).$$

The principles are equivalent: If we define $\Psi(n)\equiv \forall k\le n\colon \Phi(n)$, then we imemdiately get $\Psi(n)\implies \Psi(n+1)$ from $(1)$.

---

Remark: An overlooked and somewhat tricky part is hidden in your bold "A diagonal is drawn ...". It is a not fully trivial (but true) fact that every (not necessarily convex) polygon has a diagonal.