# Number of straight line segments determined by $n$ points in the plane is $\frac{n^2 - n}{2}$

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?

-
No, you start with zero points, not zero lines. You are proving a formula for the number of lines. There is no number of points that gives you 4 lines... – Thomas Andrews Mar 15 '13 at 17:33
The first thing I would observe here is that the number of lines is just the number of unordered pairs of points. – Michael Hardy Mar 15 '13 at 17:44

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$.

-
I thought you were me for a second...Nice avatar! – 1015 Mar 15 '13 at 21:57

Say you've got $k$ points and the number of unordered pairs of them---hence the number of lines---is $\dfrac{k^2-k}{2}$.

Add a $(k+1)$th point. You can pair the new point with any of the old $k$ points, getting $k$ new lines.

So the number of lines is now $$\frac{k^2-k}{2} + k.$$

So now all you need is to prove that that's the same as $\dfrac{(k+1)^2-(k+1)}{2}$.

-

P(n): 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: $\large \frac{n^2 - n}{2}$.

Inductive hypotheses: given $n = k$ points, assume $P(k)$ is true: $P(k) = \dfrac{k^2 - k}{2}$.

Proving $P(k+1)$ would require proving that for $n = k+1$ points, using your inductive hypothesis, the number of lines passing through $k + 1$ points is equal to

$$P(k+1) = \dfrac{(k+1)^2 - (k+1)}{2}$$ That is, $P(k+1)$ is the sum of $P(k)$, the number of lines determined by $k$ points, plus the number of additional line segments resulting from the additional point: the $(k+1)$th point. Since there are $k$ original points, the number of line segments that can connect with the $(k+1)$st point is precisely $k$, one line segment connecting each of the $k$ original points with $k+1$th point.

That is, our sum is:

\begin{align}P(k) + k &= \dfrac{(k^2 - k)}{2} + k = \dfrac{(k^2 - k)}{2} + \dfrac {2k}{2} \\ \\ & = \dfrac{ k^2 + 2k - k}{2} \\ \\ & = \frac{k^2 + 2k +1 - k - 1}{2} \\ \\ & = \frac{(k+1)^2 - (k + 1)}{2} \\ \end{align}

Hence, from the truth of the base case, and the fact that $P(k+1)$ follows from assuming $P(k)$, we have thus proved by induction on $n$ that $P(n) = \dfrac{n^2 - n}{2}$

-

Assume you are given $n+1$ points. Label them $a_1,\ldots,a_{n+1}$. How many lines pass through $a_{n+1}$? Now use the induction hypothesis for $a_1,\ldots,a_n$. Since any line segment either passes through $a_{n+1}$ or not - the sum of those numbers will be $P(n+1)$

-