Solution: 2015 Winter Midterm - 6
Author: Michiel SmidQuestion
$\newcommand{\Silly}{{\rm S \scriptsize ILLY}}$
What does
$$
\sum_{k=2}^{n-1} (k-1)(n-k)
$$
count?
(a)
The number of 3-element subsets of an $(n+1)$-element set.
(b)
The number of 3-element subsets of an $(n-1)$-element set.
(c)
The number of 3-element subsets of an $n$-element set.
(d)
The number of times you fart when running algorithm $\Silly(n)$.
Solution
Let’s write it out and see what it represents if n is a small value like 5.
$\sum_{k=2}^{4} (k-1)(5-k)$
$(2-1)(5-2) + (3-1)(5-3) + (4-1)(5-4)$
$1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1$
We can rewrite in \binomial form as
$\binom{n}{3}$