Prove that for an arbitrary number of points n, it takes (n^2-n)/2 line segments to join them.?

Question

no three points are collinear (imagine them lying on the perimeter of a circle. Use mathematical induction.

Answer 1

PROOF BY INDUCATION

STEP 1: Prove the base case, n = 1.

With 1 point, you would make zero segments. Plug n into the formula and see if you get zero.
f(1) = (1² - 1)/2 = 0

Or if you don't like the base case with 1 point, start with 2 points and 1 line segment:
f(2) = (2²-2)/2 = 2/2 = 1

STEP 2: Assume the case for n points, prove it for n+1 points.
Okay, given that you have n points connected with (n²-n)/2 line segments. Now you add one more point (n+1). You need to connect this new point to the n other points so there will be n additional segments.
Assume:
f(n) = (n² - n)/2

We know the following relationship between f(n+1) and f(n):
f(n+1) = f(n) + n

Now just manipulate this to get it to look like our desired result:
f(n+1)
= (n²-n)/2 + n
Get a common denominator of 2:
= (n²-n)/2 + (2n)/2
= (n²- n + 2n)/2

We want to get to (n+1)² which is n²+2n+1... so add and subtract 1 in the numerator:
= (n² + 2n + 1 - n - 1)/2

Now you have the (n+1)² term:
= ((n+1)² - n - 1))/2

And notice that - n - 1 = -(n+1):
= ((n+1)² - (n+1))/2

This is the format we wanted for f(n+1) = ((n+1)² - (n+1))/2

STEP 3: Declare that by induction you have proven the case for n=1, and shown if you assume for n points, it is true for n+1 points. Therefore it is true for an arbitrary number of points.