# Proof by Induction

Printable View

• Oct 11th 2013, 08:08 PM
clintonh0610
Proof by Induction
If n points lie in a plane and no three are collinear, prove that there are 1/2n(n-1) lines joining these points. I'm not really sure where to even start with proving this. I'm supposed to use proof by induction. Any help would be great. Thanks.
• Oct 11th 2013, 08:42 PM
ibdutt
Re: Proof by Induction
something appears to be wrong in the question because 1/2n(n+1) is a fraction and number of lines cannot be in fraction.
• Oct 12th 2013, 03:56 AM
Plato
Re: Proof by Induction
Quote:

Originally Posted by clintonh0610
If n points lie in a plane and no three are collinear, prove that there are 1/2n(n-1) lines joining these points. I'm not really sure where to even start with proving this. I'm supposed to use proof by induction. Any help would be great.

There is nothing wrong with the formula. It just written poorly.
It is $\binom{n}{2}=\frac{n(n-1)}{2}$. To prove that by induction is a pain.

The base case $n=1$ is trivial: there is no line segment.

Suppose it is true for $n=K$, there are $K$ points and $\frac{K(K-1)}{2}$ line segments.

If you add one more point, then how many new line segments are added?

See if you can get $\frac{(K+1)(K)}{2}~?$