What is wrong with the following induction argument?

Question

I found a problem on a note on induction. The problem went like this:

"Let $n$ be a non-negative integer. Suppose we are given a triangle and n points inside it, with no three of the given $n + 3$ points collinear. We divide the triangle into smaller triangles, using the $n + 3$ points as vertices. Show that we always end up with $2n + 1$ triangles."

A proposed solution followed the problem:

"For the base case $n = 0$, there is clearly $2n + 1 = 1$ triangle. For the inductive step, assume that $k$ points inside the triangle define $2k + 1$ triangles. If we add a point $x$, as shown, then we lose one triangle but create three more triangles, for a net addition of two triangles. Hence, there are a total of $2k + 1 + 2 = 2k + 3 = 2(k + 1) + 1$ triangles, which completes the induction."

According to the note, this solution has a 'major conceptual flaw' and I can't seem to find it. Is it the base case?

Any help will be appreciated. Thanks in advance!

Answer 1

The statement we are to prove is not that we can partition the triangle into $2n + 1$ triangles using the $n + 3$ points as described. Rather, it says that if we do partition the triangle using the $n + 3$ points as described, the result will always be $2n + 1$ triangles.

The argument fails because there are partitions of the triangle that can be done using some sets of $n + 3$ points that cannot be derived by the method given in the "proof." Therefore we don't know that the statement holds for those partitions.

Here is a partition of a triangle for the case $n = 3$ that cannot be generated by adding one point to an existing partition for the case $n = 2$:

The construction in the "proof" can generate only partitions in which at least one of the additional $n$ vertices has only three edges meeting at it.

As it so happens, this example is still a partition into $2n + 1$ triangles, but there is nothing in the "proof" to say that this is more than a happy coincidence, or that it will continue to hold true for partitions of larger sets of points that the construction of the "proof" cannot generate.