Quarantine And Bijections – Mattia Giuri's bizarre blog

Now the majority of Italy is in lockdown again. So, why not spend some time doing combinatorics.

Today’s subject is bashing sums without having to do any calculation.

Let’s say we have this sum:

$\sum_{n=0}^{100} n^2 {100 \choose n}$

One way to do it would be differentiating $(1+x)^{100}$ , then multiplying the result by x and differentiating again. Then we get an expression with variable x, and by substituting 1 we get the desired result.

But we are artists, not butchers. So, think about this. The problem is equivalent to choosing a subset of people among 100, and then choosing a president and a vice president among them (president and vice president can be the same person).

Hence, we count it another way. Let’s first choose the president and vice president. Remember that $2^n$ is the number of subsets in a set with n elements.

If they are the same person, then we get $100 \cdot 2^{99}$ total cases, if they are not we have $100 \cdot 99 \cdot 2^{98}$ cases.

Summing them, we get the result.