# induction triangle question prove x triangles are formed

Prove with induction: Given n non parallel lines such that no three intersect at a point, there are c(n,3) triangles formed.

so I have n!/(n-3)!3! triangles if this condition holds, that is all I understand how to do from this question

The inductive proof is to start with the base case: with three lines you get one triangle. Now assume it is true for $k$ lines, so there are $C(k,3)$ triangles . Add another line. It will form $\frac 12 k(k-1)$ new triangles. Add these in and show that this gives a total of $C(k+1,3)$
• Hm..why does adding one extra line to k lines form $1/2k (k+1)$ lines? I thought of a strong induction proof but this seems better. – Daniel Cook Nov 12 '13 at 19:53
• Are you sure the number of new triangles formed depends on the number of lines? I think it depends on how many new triangles $k$ lines form. If the number of new triangles $k$ lines form is $x$, then the number of triangles formed by $k+1$ lines is $1/2x(x+1)$. Am I mistaken? I apologize if I am. – Daniel Cook Nov 15 '13 at 22:38
• Each new line will cross all the previous lines. It will therefore make a new triangle with each pair of existing lines. But I just realized that the plus sign should be a minus, because from $k$ lines one can form $\frac 12k(k-1)$ pairs. Incidentally, please write it as $k(k+1)/2$ or $(1/2)k(k+1)$ or use \frac to stack the fraction. With the slash it is not clear what is in the denominator. We get various things on this site. – Ross Millikan Nov 15 '13 at 23:09
• That makes a lot more sense now! Because $\frac 12 k(k+1)$ is the $k^{th}$ triangular number, I got confused. The triangular numbers actually represent how many new triangles are formed, don't they? And, I will from now on, thank you so much. – Daniel Cook Nov 15 '13 at 23:33