As the festive seasons is coming to a close and we've seen out all twelve days of Christmas I found myself thinking about the famous carroll of the same name. Namely, how many presents in total did my true love give to me? This is can be given by the nested summation
$\sum \limits_{i=1}^{12} (\sum \limits_{j=1}^i j)$ ,
where the inside sum is the number of presents received each day (i.e a partridge in a pear tree on the first day, two turtle doves and a partridge in a pear tree on the second day, etc.) and the outside summation sums over the days. This can be found to be 364, but what about in general for $n$ days of Christmas?
Well we can generalise the summation by just inserting $n$ into the summation and solving it.
$\sum \limits_{i=1}^{n} (\sum \limits_{j=1}^i j)$
Using the well known solution of the sum $~ \sum \limits_{i=1}^{n}i = \frac{n(n+1)}{2} ~$ we can obtain a non-nested sum,
$ = \sum \limits_{i=1}^{n} \frac{i(i+1)}{2} = \sum \limits_{i=1}^{n} (\frac{1}{2}i^2 + \frac{1}{2}i )$ ,
which we can split into separate summations
$ = \frac{1}{2} \sum \limits_{i=1}^{n} i^2 + \frac{1}{2}\sum \limits_{i=1}^{n}i = \frac{n(n+1)(2n+1)}{12}+ \frac{n(n+1)}{4} = \frac{n(n+1)(2n+1) + 3n(n+1)}{12} = \frac{2n^3 + 6n^2 + 4n}{12} = \frac{n(n+1)(n+2)}{6}$
which we notice can be written as the binomial coefficient,
$ = {n+2\choose3}$.
This doesn't really come as any surprise since this kind of problem seems like the prime candidate for one which could be solved using some fancy combinatorics to yield a binomial coefficient. But if we notice now that we can write the standard arithmetic series sum as a binomial coefficient, eg.,
$~ \sum \limits_{i=1}^{n}i = \frac{n(n+1)}{2} = {n+1\choose2} ~$
we might notice a similarity between them.
Similarly it can be shown that for a twice nested sum we have,
$\sum \limits_{i=1}^{n} (\sum \limits_{j=1}^i (\sum \limits_{k=1}^j k)) = {n+3\choose4} $.
In general it seems for an $(m-1)$-th nested sum (i.e, one which has $m$ summation symbols) we have,
$\sum \limits_{i_1=1}^{n} \sum \limits_{i_2=1}^{i_1} \sum \limits_{i_3=1}^{i_2} \dots \sum \limits_{i_m=1}^{i_{m-1}}i_m = {n+m\choose1+m} $
and this is likely provable with induction.
My question is to you is, how can this relationship between binomial coefficient and summations be thought of? That is to say, why would taking the number of possible pairs of $n+1$ elements happen to give you the sum from $1$ to $n$? And how does this somehow seem to extent with nested summations; the number of ways you can take 3 elements from $n+2$ gives you the first nested summation and so on? I'm sure some combinatorics whizz will be able to rearrange the way we count these sums somehow to yield the answer. Anyway at the very least it's interesting to think about - happy holidays!