Any polygon can be split into triangles, so any $n\!-$triangulate for any $n$ will always be composed of triangles.
Given an $(n-1)$ triangulate, we can add the point in the following three ways:
- The point lies on a point that is already there. In this case, the point has already been connected to all possible vertices that it can be connected to (since we started with a $(n-1)$ triangulate). Example:
- The point lies on a line that is already there, but not on a point. In this case, since the line is the common edge of at most $2$ triangles, the point can only be connected to $2$ vertices (the opposite ends of the triangles). For example:
- This creates $4$ new triangles, but destroys the original $2$ triangles. Thus, the number of triangles increase by $2$. This is an optimal case.
- The point lies inside of a triangle. The new point can then be connected to exactly $3$ vertices of the bounding triangle. Example:
- This creates $3$ new triangles, but destroys the original triangle. So, the number of triangles increase by $2$. So, this is also an optimal case.
We can see that the $n^{th}$ triangulate has exactly $2$ more triangles than the $(n-1)^{th}$ triangulate.
This gives us the following recurrence: $$T(n)=T(n−1)+2,T(2)=5$$
Which solves to: $$\boxed{T(n) = 2n + 1}$$
Hence, option d is the correct answer.