How many triangles has a complete graph. Recursive Equation

Question

I need to find the solution with a recursive equation. I found the solution with combinations: $${n}\choose{}3$$

but I don't know how to find it with recursive equations. I don't find a pattern to resolve it

Thanks

Answer 1

Let $T_n$ be the number of triangles in a complete graph of size $n$ for $n\geq 3$. Deduce that $T_{n+1} = T_n + \binom{n}{2}$, as it amounts to considering if a triangle is contained in the complete subgraph on $n$ vertices or not. With $T_3=1$, it follows that $T_n=1+\sum_{k=3}^{n-1}\binom{k}{2}=1+\sum_{k=3}^{n-1}k(k+1)/2$. Simplifying this will give you the answer.