Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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

4 Answers 4

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

share|improve this answer
    
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}$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.