# Is it true that $\sum_{k=3}^{n}\binom{n}{k}\binom{k}{3} = \binom{n}{3}\binom{n-3}{k-3}$?

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?

• 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. – 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.

• $$\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}$$ – 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}$.