# Proof by induction: n choose 3 triangles are formed by n lines

• Nov 15th 2013, 01:58 PM
extremez
Proof by induction: n choose 3 triangles are formed by n lines
Prove: n choose 3 triangles are formed by n lines such that no 3 lines can intersect at the same point. I'm required to prove this by induction, I know it's really easy to prove without it.

I know the base case, but the induction step seems tricky. I'm finding it hard to figure out how many new triangles form when one new line is added, and even if I do, I'm not sure how to make the sum equal k+1 choose 3. Can anyone help me with this proof? Thank you.
• Nov 15th 2013, 02:08 PM
Plato
Re: Proof by induction: n choose 3 triangles are formed by n lines
Quote:

Originally Posted by extremez
Prove: n choose 3 triangles are formed by n lines such that no 3 lines can intersect at the same point. I'm required to prove this by induction, I know it's really easy to prove without it.

As stated that is a false statement.

Consider \$\displaystyle n\$ distinct parallel lines.