Lesson 1

In the previous two problems, we derived \(A(n)\) not from \(A(n-1)\), but from \(A(n-t)\) for some \(t\). In general, this is called the method of complete induction (also known as strong induction). To prove the statement “\(A(n)\) holds for all integers \(n \ge \alpha\)” using the method of complete induction, one needs, as usual, to check the base case (i.e., that \(A(\alpha)\) holds), and in the induction step, when proving \(A(n+1)\), to assume that not only \(A(n)\) holds, but all previous statements hold: \(A(\alpha), A(\alpha+1), \dotsc, A(n)\).

For example, we used the method of complete induction to prove that any integer \(m \ge 8\) can be represented as a sum of threes and fives: we derived \(A(m)\) from \(A(m-3)\) (for \(m \ge 11\)). Here is another problem where it is useful to use not only the immediately preceding statement.

A convex \(n\)-gon (\(n \ge 3\)) is divided into triangles by non-intersecting diagonals. Prove that \((n-2)\) triangles are obtained.

Problem. Is this a correct proof?

The base case \(n=3\) is clear. For the induction step \(n-1 \to n\), consider a convex \(n\)-gon. One of its diagonals divides it into a triangle and a (convex) \((n-1)\)-gon. By the induction hypothesis, the number of triangles is \[1+(n-1-2)=n-2.\]