I ask this question in reference to the question asked here. The answers included the solution $\binom{n}{4}$ to the question of how many intersection points there are if you connect $n$ points on a circle with each other and only two chords intersect at a given intersection. Additionally, there was a hint on how to prove it, using mathematical induction.
My work so far
I've given it a try, but it seems I'm rather stuck at the step of the induction. Here's my approach:
For $n=0$ and $n=1$, there is no chord at all, so there can't be an intersection. For $n=2$ there is only a single chord, again allowing for no intersection.
For $n=3$, we start by looking at a circle with $n=2$ points and no intersection. When we now add the third point, the two newly created chords can only touch the existing chord at its two end points, allowing for no intersection (in our definition).
For $n \geq 4$, we use induction:
Basis: n = 4
We start by looking at a circle with three points and no intersection. Note how the three existing chords separate the circle into four distinct areas, of which three are limited by the circumfrence.
A new, fourth point chosen somewhere on the circumfrence will be on the one side of such a separating chord, allowing it to connect to two points without intersection. Yet there's always a third existing point which is on the other side of that separating chord, calling for an intersection of the last newly created chord with the separating chord.
Precondition: Our formular holds for an arbitrary, yet fixed $n \in \mathbb{N}$.
Step: Have to show that it holds for $n+1$
Starting with a circle that has only $n$ dots chosen, we know from the precondition that it must have $\binom{n}{4}$ intersections. Now we add the last point in.
The issues
I now find it difficult to prove this step, since trying to argue using separating chords gets too complicated too quickly.
Jay gave a hint that said to utilize this formular for the proof:
$$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}$$
Since in this case $k=4$, and we already found $\binom{n}{4}$ as the number of intersections in a circle with $n$ points, that means when we add another point, there must be $\binom{n}{3}$ more intersections. But how would you prove that?
Additionally, it might be necessary to prove that choosing a group of four of the points actually leads to finding exactly one intersection. I don't think it's a trivial fact, since, depending on how you choose the chords of the four points, you might also end up with no intersection.
If you draw $k$ chords on a circle, one at a time, then you can count intersections. To get the maximum, each time you add a chord, you try to intersect every previous chord. So at the $m$th chord you add at most $m-1$ intersections:
1st chord: 0 intersections
2nd chord: 1 new intersection
3rd chord: 2 new intersections
etc.
So you end up with
$$0+1+2+\cdots+(k-1) = \frac{k(k-1)}{2}={k\choose 2}$$
total intersections (at most.)
Now, how many chords are there? Given $n$ points, every pair gives a different chord, so the number of chords is $k = {n\choose 2}.$
So the maximum number of intersections is
$${ {n \choose 2}\choose 2}.$$
Show that this is less than $n \choose 4.$