0
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.