Dear Uncle Colin,

I’ve got a question that asks me to find the coefficient of $x^5$ in $(1+x)^5 + (1+x)^6 + (1+x)^7 + … + (1+x)^{100}$.

I can easily work out the coefficient in each term (it’s just $\nCr{k}{5}$), but I can’t see an easy way to add them up. Any ideas?

- Perhaps A Simple Calculation Answers Logically

Hi, PASCAL, and thanks for your question!

There is indeed an easy way to add them up, and I think the simplest way to see this is to work through the first few terms.

The sum you have is $\nCr {5}{5} + \nCr {6}{5} + \nCr {7}{5} + … \nCr{100}{5} = 1 + 6 + 21 + 56 + … + $ (something pretty big I can’t be bothered to work out right now). That’s the fifth diagonal of Pascal’s Triangle ((Hey! That’s your name!)), depending on how you count.

The partial sums of that sequence are 1, 7, 28, 84, … - which is the sixth ((or, at least, next)) diagonal of Pascal’s Triangle!

Ninja aside

All you need to do is work out $\nCr {101}{6} = \frac{(101)(100)(99)(98)(97)(96)}{720}$.

The first five factors on top are $(100+1)(100)(100-1)(100-2)(100-3) = (100)(100^2-1)(100^2 - 5(100)+6)$.

That simplifies further to $100^5 - 5(100^4) + 5(100^3) + 5(100)^2-6(100)$. Now, $\frac{96}{720} = \frac{4}{30}$, so we’ve got $\left(10^9 - 5\times 10^7 + 5\times 10^5 + 5\times 10^3 - 6\times 10^1\right)\times \frac{4}{3}$. The big bracket is 950,504,940; a third of that is 316,834,980; four times that is 1,267,339,920.

Back to our regularly scheduled whotsit

In general, the sum of the first $k$ terms in the $n$th diagonal of Pascal’s Triangle, $\sum_{i=n}^{k-n+1} \nCr k n = \nCr {k+1}{n+1}$ - which you can prove pretty simply by induction.

Hope that helps!

-Uncle Colin