How can we prove by les-grizzlys-catalans.orgematical 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 $\fracn^2 - n2$? (The line segment determined by two points is the line segment connectingthem.)

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?

discrete-les-grizzlys-catalans.orgematics proof-writing induction
Share
Cite
Follow
edited Feb 16 "14 at 16:37 amWhy
asked Mar 15 "13 at 17:30 Muath05Muath05
$\endgroup$
3

3
$\begingroup$
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 $\fracn^2-n2$.

You are watching: The number of segments determined by n points is

When there is $1$ point, there are $0=\frac1^2-12$ line segments. Hence we have $P(1)$.

Now suppose we have $P(k)$ for some positive integer $k$. Then $k$ points determine $\frack^2-k2$ line segments. When we add another point, we connect this point to each of the existing $k$ lines. So now we have $\frack^2-k2+k=\frack^2-k+2k2=\frack^2+k2=\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
Cite
Follow
answered Mar 15 "13 at 17:38
user4594user4594
$\endgroup$
1
3
$\begingroup$
Say you"ve got $k$ points and the number of unordered pairs of them---hence the number of lines---is $\dfrack^2-k2$.

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$$\frack^2-k2 + k.$$

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

Share
Cite
Follow
answered Mar 15 "13 at 17:46 Michael HardyMichael Hardy
1
$\endgroup$
2
$\begingroup$
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 \fracn^2 - n2$.

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

See more: How Many Pennies Are In 100 Dollars ? How Many Pennies Are In 100 Dollars

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:

\beginalignP(k) + k &= \dfrac(k^2 - k)2 + k = \dfrac(k^2 - k)2 + \dfrac 2k2 \\ \\& = \dfrac k^2 + 2k - k2 \\ \\ & = \frack^2 + 2k +1 - k - 12 \\ \\& = \frac(k+1)^2 - (k + 1)2 \\\endalign

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) = \dfracn^2 - n2$