Derive a recurrence relation to represent the number of intersection points formed by the diagonals of a convex polygon with n vertices. Show that the solution of the recurrence relation is $\binom n4$.
I have derived the recurrence relation but failed to get its solution. The relation is $R_{n+1} = R_{n}+\sum _{k=2}^{n-1}(k-1)(n-k); R_{4} = 1$.
I tried to use generating function to solve it.
The relation is $\;R_{n+1} = R_{n}+\sum _{k=2}^{n-1}(k-1)(n-k); \;R_{4} = 1\,$.
First off:
$$ \begin{align} \sum _{k=2}^{n-1}(k-1)(n-k) = \sum _{k=1}^{n-2} k(n-k-1) &= (n-1) \cdot \sum _{k=1}^{n-2}k - \sum _{k=1}^{n-2} k^2 \\ &= (n-1) \cdot \frac{(n-2)(n-1)}{2} - \frac{(n-2)(n-1)(2n-3)}{6} \\ &= \frac{n(n-1)(n-2)}{6} \\ &= \binom{n}{3} \end{align} $$
(The combinatorial interpretation of this is fairly straightforward: when adding the $\,(n+1)^{th}\,$ vertex to the previous $n$-gon, the new intersections of diagonals are precisely those where one of the diagonals originates at the newly added vertex.)
Then, telescoping:
$$ \begin{align} R_n &= R_{n-1} + \binom{n-1}{3} \\ &= R_{n-2} + \binom{n-2}{3} + \binom{n-1}{3} \\ & \cdots \\ &= R_4 + \binom{4}{3}+\binom{5}{3}+\ldots + \binom{n-2}{3} + \binom{n-1}{3} \\ &= \binom{3}{3} + \binom{4}{3}+\binom{5}{3}+\ldots + \binom{n-2}{3} + \binom{n-1}{3} \\ &= \binom{n}{4} \end{align} $$
The last step used the hockey-stick identity $\displaystyle {\binom {n+1}{k+1}}=\sum_{j=k}^{n} \binom{j}{k}\,$.
