Exercise 409Combinatorics › Binomial coefficientsHigh schoolAdded 3 Nov 2026

Recurrence for coefficients

#recurrence#Pascal#coefficients

Statement

Let $a_n=\binom{n}{2}$ . Find a recurrence for $a_n$ and solve it.

Hint

$\binom{n}{2}=\binom{n-1}{2}+(n-1)$ , or use $a_n-a_{n-1}=n-1$ .

Show solutionHide solution

Recurrence. $a_n-a_{n-1}=\binom{n}{2}-\binom{n-1}{2}=n-1$ (from Pascal: $\binom{n}{2}=\binom{n-1}{1}+\binom{n-1}{2}$ ).

Solve. $a_n=\sum_{k=1}^{n}(k-1)+a_1=\frac{n(n-1)}{2}$ .

Conclusion. $a_n=\frac{n(n-1)}{2}$ .