Prove by induction that the expression for the number of diagonals in a polygon of n sides is n*(n-3)/2.

GATE 1998 · Discrete Mathematics · Relations · medium

Answer: Number of diagonals in an n-gon = n*(n-3)/2, proved by induction.

1. Base case n=4: A quadrilateral has exactly 2 diagonals (the two cross-diagonals). Formula gives 4*(4-3)/2 = 4*1/2 = 2. Base case holds.
2. Inductive step: Assume D(n-1) = (n-1)*(n-4)/2. Adding the nth vertex: it is adjacent to 2 vertices, and is the vertex itself, so it connects as a diagonal to (n-1)-2 = n-3 existing vertices. Thus D(n) = D(n-1) + (n-3) = (n-1)*(n-4)/2 + (n-3) = [(n-1)*(n-4) + 2*(n-3)] / 2 = [n^2 - 5n + 4 + 2n - 6] / 2 = [n^2 - 3n] / 2 = n*(n-3)/2. QED.