Hint for a combinatorial statement for counting triangles

440 Views Asked by At

enter image description here

I know it is asking me to prove it works for the total number of triangles. I notice a pattern which is $$T_n = n^3$$ but this doesn't seem to help me in anyway.

Edit: I also notice that the lines increase by 2 each time, creating 3 more intersections each time.

2

There are 2 best solutions below

2
On

Hint:

Note that every triangle in $T_n$ has at least one of the vertices of the base angles.

Besides, every triangle can be determined by exactly 3 lines in $T_n$. However, if you choose 3 lines intersecting at one point, you will not get a triangle.

Based on these facts, you can either write it down as $\displaystyle\binom{2n+1}3-2\binom{n+1}{3}$ or $\displaystyle2\binom{n}2\binom{n}1+n^2$, both of which produce $n^3$.

0
On

Alternative solution :

Note : This doesn't explain the combinatorial identity in the question. I only give alternative way to arrive at $T_{n}=n^3$.

I'll use that given $m$ points on a straight line and one point not on the line, total number of triangles formed is $\binom{m}{2}$.

Note, every triangle includes at least one base vertex. For $n$th diagram, number of points on any non-base line $= n+1$ and there are $n$ such lines.

Triangles including left vertex $ = n\binom{n+1}{2}$

Remaining triangles with right vertex $ = n\binom{n}{2}$

Hence $T_{n} = n\{\binom{n+1}{2}+\binom{n}{2}\} = n^3$.