How can we prove by mathematical induction that for all $n$, the number of straight line segments determined by $n$ points in the plane, no three of which lie on the same straight line, is $\frac{n^2 – n}{2}$? (The line segment determined by two points is the line segment connecting
them.)
I know we start with the base case, where, if we call the above equation $P(n)$, $P(0)$, for $0$ lines would be $0$. But I really have no idea how to begin the inductive step. How do we know what $k+1$ we're supposed to arrive at?
Best Answer
Let $P(n)$ be the statement that the number of straight line segments determined by $n$ points in the plane no three of which lie on the same straight line is $\frac{n^2-n}{2}$.
When there is $1$ point, there are $0=\frac{1^2-1}{2}$ line segments. Hence we have $P(1)$.
Now suppose we have $P(k)$ for some positive integer $k$. Then $k$ points determine $\frac{k^2-k}{2}$ line segments. When we add another point, we connect this point to each of the existing $k$ lines. So now we have $\frac{k^2-k}{2}+k=\frac{k^2-k+2k}{2}=\frac{k^2+k}{2}=\frac{(k+1)^2-(k+1)}{2}$ line segments. This means that we have $P(k+1)$.
Hence we have $P(n)$ for all positive integers $n$.