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 Triangle1, depending on how you count.
The partial sums of that sequence are 1, 7, 28, 84, … - which is the sixth2 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