# Proof by Induction - Triangles

Given n non-parallel lines such that no three intersect at a point, there are n choose 3 triangles formed.

So far what I come up with is by using proof by induction:

Base Case: For every three lines a triangle is formed.
Inductive Hypothesis: Assume true for k line.
Inductive Step: Suppose that it holds for k lines, show true for k+1 lines.


But how do I show true for k+1 lines? Did I make a mistake in what I have in my induction proof so far? Any help is appreciated, and I don't need a direct solution, just how to begin will suffice.

• Your problem seems tautological. 3 non-parallel lines that do not intersect in a point will form a triangle. There are n choose 3 ways to choose 3 lines out of n. So there will be n choose 3 triangles. – NovaDenizen Nov 19 '13 at 1:50

If this was a homework assignment in a class trying to teach induction, you should complain. You wrote already the main point: For every three lines, there is a triangle formed. The converse, of course, is also true: for every triangle formed, there are three lines. This establishes a bijection between $\{$triangles$\}$ and $\{$unordered triples of lines$\}$. But the number of unordered triples of elements from an $n$-element set (in this case the set of lines) is precisely $\binom n 3$ — this is the definition "choose".

The reason I could imagine this being assigned in a class on induction is that it's not uncommon to use stupid definitions (they are not stupid, but rather important and deep, as facts, but should not be taken as the definition) of binomial coefficients. Two facts, sometimes taken as definitions, are that $\binom n 3 = \frac16 n^3 - \frac12 n^2 + \frac13 n$, and that $\binom{n+1}3 = \binom n 3 + \binom n 2$. Although both of these can be proved by induction, the most natural proofs are not inductive. In any case, I could imagine an instructor looking for an argument like: by induction, there are $\binom n 3$ triangles formed from $n$ lines; adding another line creates a triangle for each of intersection among the original lines; there are $\binom n 2$ such intersections (why? by induction there there are $\binom n 2$ intersections among $n$ lines, and adding a line creates $n$ new intersections, and $\binom n 2 + n = \binom {n+1}2$); therefore there are $\binom n 3 + \binom n 2 = \binom{n+1}3$ triangles formed from $n+1$ lines.

But that inductive argument is stupid compared to the one-line argument that triangles correspond to triples.

• Thank you so much, this was very helpful. – Sc4r Nov 19 '13 at 2:00

You are doing great so far, yes this is exactly right.

Suppose it holds for $k$ lines and we have $k+1$ lines. Take out any one of these lines and make it special say line $L$.

Now by your inductive hypothesis there are ${k \choose 3}$ triangles formed that do not use the line $L$ at all.

So now you just have to count how many triangles use line $L$. To do this you should note that you need two more lines to make a triangle, but I won't spoil all the fun.