I was asked to find a closed formula for $$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$$ To remove the $\sum$ if you will.

Here's my reasoning, let's say we have a football team with $n$ players. First we choose $k$ players from those $n$ to be on the starting lineup, and then we chose $3$ out of those $k$ players to play defense.

That is what $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3}$ means (I think).

Now, that is the same thing as first choosing $3$ out of the initial $n$ to play defense, and then choosing $k-3$ out of the remaining $n-3$ to be on the starting lineup, and that's $\binom{n}{3}\binom{n-3}{k-3}$, so I inferred from that:

$$\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$$ is this true?

  • 2
    $\begingroup$ You're on the right track, but here's an easy way of seeing that your current form can't be correct: your left hand side is a function of $n$ only; $k$ is a bound variable, since it's being summed over. But you've inserted a $k$ into the RHS, so it's a function of both $n$ and $k$, not of $n$ alone. $\endgroup$ – Steven Stadnicki Feb 5 '14 at 16:55

You've proved a version of the trinomial revision identity. However, you accidentally dropped the summation; what is true is $${n\choose k}{k\choose 3}={n\choose 3}{n-3\choose k-3}$$

Now you may pull the ${n\choose 3}$ out of the sum, reindex, and use another well-known identity on binomial coefficients.

  • 1
    $\begingroup$ $$\sum_{k=3}^{n}\binom{n}{3}\binom{n-3}{k-3}=\binom{n}{3}\sum_{k=0}^{n}\binom{n-3}{k} = \binom{n}{3}2^{n-3}$$ $\endgroup$ – Oria Gruber Feb 5 '14 at 17:00

Your football team combinatorial argument, with some modification, will work. We have a team of $n$ people. We want to select $3$ of them to get a gold medal, and a subset (possibly empty) of the rest to get a silver medal.

We count the number of ways to do this in two different ways.

(1) The gold medal winners can be chosen in $\binom{n}{3}$ ways. For every such way, the set of silver medal winners can be chosen in $2^{n-3}$ ways, for a total of $\binom{n}{3}2^{n-3}$ ways.

(2) For any $k\ge 3$, we can choose the $k$ people who win some medal in $\binom{n}{k}$ ways, and for every choice we can choose the gold medal winners from these in $\binom{k}{3}$ ways, for a total of $\binom{n}{k}\binom{k}{3}$ ways. Since we are free to choose any number $k\ge 3$ to get some medal, the total number of ways to select the gold and silver medal winners is $\sum_{k=3}^n \binom{n}{k}\binom{k}{3}$.


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.