Let $A(n)$ be the maximum number of intersections of $n$ lines. Show through induction that the following holds:

Question

The following holds:

$$A(n)=\sum_{k=0}^{n-1}k$$

How to do the induction?

Answer 1

Let $A(n)$ be the maximum number of intersections of $n$ lines.

Claim: $A(n) = \dfrac{n(n-1)}{2}, n \ge 2$.

Proof: By induction on $n \ge 2$. The base case $n = 2$. $A(2) = 1$, and $\dfrac{2(2-1)}{2} = 1$. So it is true for $n = 2$. Assume the statement is true for $n \ge 2$, you show it is also true for $n+1$ lines. For any $n+1$ lines. Take any $n$ lines among them, the maximum number of intersections from inductive step is $A(n) = \dfrac{n(n-1)}{2}$. For the remaining line, it has at most $n$ intersections with the other $n$ lines. So the maximum total of intersections is $\dfrac{n(n-1)}{2}+n=\dfrac{(n+1)n}{2}\implies A(n+1) = A(n) + n= \dfrac{(n+1)n}{2}$. Hence by induction we're done.