Sum involving binomial coefficients.

Question

Prove that $${^{404}\mathrm C_4}-{^4\mathrm C_1}\cdot{^{303}\mathrm C_4}+{^4\mathrm C_2}\cdot{^{202}\mathrm C_4}-{^4\mathrm C_3}\cdot{^{101}\mathrm C_4} =(101)^4$$

I tried writing $101=102-1$, but couldn't move forward.

Answer 1

The question is equivalent to:

You have $4$ groups with $101$ items in each group.

What is the number of ways for selecting $4$ items, where each item is from a different group?

---

The given solution uses inclusion/exclusion principle:

• Include the number of ways for selecting $4$ items from up to $\color\red4$ groups: $\binom{4}{\color\red4}\cdot\binom{101\cdot\color\red4}{4}$
• Exclude the number of ways for selecting $4$ items from up to $\color\red3$ groups: $\binom{4}{\color\red3}\cdot\binom{101\cdot\color\red3}{4}$
• Include the number of ways for selecting $4$ items from up to $\color\red2$ groups: $\binom{4}{\color\red2}\cdot\binom{101\cdot\color\red2}{4}$
• Exclude the number of ways for selecting $4$ items from up to $\color\red1$ groups: $\binom{4}{\color\red1}\cdot\binom{101\cdot\color\red1}{4}$

---

Of course, a simpler solution would be to simply choose one item from each group: $101^4$.

Answer 2

The given expression here is the coefficient of $x^4$ in $P(x) := ((1+x)^{101}-1)^4$. You can see this by first expanding $(y-1)^4$, then putting $y = (1+x)^{101}$ and expanding it in terms of $x$.

But $P(x) =((1+101x+...)-1)^4 = (101x+...)^4 = 101^4\cdot x^4(1+...)^4$ where the dots represent higher powers of $x$.

Thus, the coefficient of $x^4$ in $P(x)$ is indeed $101^4$.