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
Best Answer
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.