Intuition behind sums of sums of whole numbers

Question

So I was playing around, and all this is just a curiosity and nothing serious.

Anyway, most readers probably know: $$1+2+3+4+5+...+(n-1)+n=\frac{1}{2}n^{2}+\frac{1}{2}n=\binom{n+1}{n-1}$$

I started playing around, adding the individual sums of whole numbers instead of whole numbers alone. Words aren't very helpful to describe this process, instead consider the sum of sums for $n=4$, which we shall call $N_2(4)$ for simplicity: $$\left ( 1+2+3+4 \right ) + \left ( 1+2+3 \right ) + \left ( 1+2 \right ) + \left ( 1 \right ) = 20$$

Remarkably, there is a simple formula (I did the math): $$N_{2}(n)=\binom{n+2}{n-1}$$

Where $N_2(n)$ is the sum of sums as above. Formally, $N_2(n)=\sum_{1\leq i}^{n}\sum_{1\leq j\leq i}j$.

Now imagine going further, with sums of sums of sums, for instance: $$N_3(4) = \left ( \left ( 1+2+3+4 \right ) + \left ( 1+2+3 \right ) + \left ( 1+2 \right ) + \left ( 1 \right ) \right ) + \left ( \left ( 1+2+3 \right ) + \left ( 1+2 \right ) + \left ( 1 \right ) \right ) + \left ( \left ( 1+2 \right ) + \left ( 1 \right ) \right ) + \left ( \left ( 1 \right ) \right ) = 35$$

Again, this seems to follow the pattern (I haven't explicitly checked): $$N_3(n)=\binom{n+3}{n-1}$$

And we might conjecture: $$N_k(n)=\binom{n+k}{n-1}$$

One angle of attack is this: realizing that the previous series always adds up to that of the differences between successive elements of the next series, and so verifying that:

$$\binom{n+k}{n-1} - \binom{(n-1)+k}{(n-1)-1}=\binom{n+(k-1)}{n-1}$$

I.e. that $N_{k}(n)-N_{k}(n-1)=N_{k-1}(n)$ for any suitable $n$ and $k$.

My question is if there's some intuition behind all this. Maybe an alternative way of looking at this, or proving it. Why are the sums so neatly expressible?

Answer 1

We can write the sum $N_2(n)$ as \begin{align*} N_2(n)&=\sum_{1\leq i}^{n}\sum_{1\leq j\leq i}j =\sum_{1\leq j\leq i\leq n}j =\sum_{1\leq j\leq i\leq n}\sum_{k=1}^j1\\ &=\sum_{\color{blue}{1\leq k\leq j\leq i\leq n}}1\\ &=\binom{n+2}{3} \end{align*}

In general we can write for $k\geq 1$: \begin{align*} N_k(n)&=\sum_{\color{blue}{1\leq j_1\leq j_2\leq \cdots\leq j_{k+1}\leq n}}1\tag{1}\\ &=\binom{n+k}{k+1} \end{align*}

In (1) we observe the index range contains all ordered $k+1$-tuples with elements from $\{1,2,\ldots,n\}$ with repetition. This number is given by the binomial coefficient $\binom{n+k}{k+1}=\binom{n+k}{n-1}$.

Answer 2

I am still not able to comment on this site, so I have to write this as an answer.

Look at the number of ways one is able to choose $2$ balls from a set of $n+1$ numbered balls.

If you chose the ball numbered one, you can choose the second ball in $n$ ways. Now, if you chose ball numbered two as the first ball, then your second ball can be chosen in $n-1$ number ways and so on. The ways of choosing the 2 balls is just $n+n-1+\cdots+1$.

Now, look at the ways of choosing 3 balls from a set of $n+2$ numbered balls. If the first ball you chose is ball number one, then the other twos balls can be chosen in $n+n-1+\cdots+1$ ways, from our last paragraph. Now, if the first ball you chose was ball number two, then the other two could be chosen in $n-1+\cdots+1$ ways and so on.

I hope you see where I'm going with this.

Answer 3

At the risk of appearing self-promotional, I think some readers looking for an elementary exposition of this topic might appreciate this article:

Dr. Michael W. Ecker, Generalized Binomial Coefficient Sums and Repetitions, MathAMATYC Educator, September 2013, Vol. 5, No. 1, p. 23-27.

In it, I also give an alternative to the classical "stars and bars" argument for counting combinations with repetitions allowed. Moreover, if nothing else, the lagniappe (bonus) number trick alone might be worth having fun with your students. (Prior to my retirement from PSU in 2016, I probably got to use that one at least once a year.)

Answer 4

I like to look at things like this in term of matrices.
Let the elements of a sequence to be summed $a_0,a_1,a_2...,a_{n-1}$ form a columnvector $A$ .
Then consider the operator (=matrix) for the partial sums $$ D = \small \begin{bmatrix} 1 & . & . & . & . & . \\ 1 & 1 & . & . & . & . \\ 1 & 1 & 1 & . & . & . \\ 1 & 1 & 1 & 1 & . & . \\ 1 & 1 & 1 & 1 & 1 & . \\ 1 & 1 & 1 & 1 & 1 & 1 \\ \end{bmatrix}$$ (Of course the size must agree with the number of elements in your sequence/vector $A$).
Then $$D \cdot A = S_1$$ gives the first-order (partial) sums; $$D^2 \cdot A = S_2$$ the second order (partial) sums and so on.
Interestingly, using the matrix-logarithm on $D$ , we can even define fractional orders, because we can define fractional powers of $D$: $$ D^h = \exp (h \cdot \log(D))$$ where we need a software which is able to compute the matrix-logarithm and the matrix-exponential (I do this in Pari/GP using the according powerseries definitions) .
Finally, we can see the $h$'th power of $D$ with the parameter $h$ symbolic:

$\qquad \Large D^h = $

$ \qquad \qquad $ ^{Here the middle coefficients are the binomial-coefficients, as for instance in the Pascal-matrix. The factorials come from the row- and column-indexes (each beginning at $0$).}

With this one can compute positive,negative, fractional and even complex orders of the generalized harmonic sums (or "hyper-harmonic sums" as Conway/Guy have christened them)

Answer 5

Before I knew math, i had my own notation for such things but i never seen it elsewhere, Let the s'th sum be $$.^s\sum_{n}n$$ be the s'th "indefinite sum of n

indefinite sum of n $\sum_{n}=F(n)$ so that $\sum_{n=a}^{b} f(n)=F(b)-F(a-1)$. The delta operator $\Delta$ is f(n)-f(n-1).

$$\Delta.^s\sum_{n}n=^{s-1}\sum_{n}n$$

$$.^s\sum_{n}n=\frac{(n+s)!}{(n-1)!(s+1)!}$$

$$\Delta.^s\sum_{n}n=\frac{(n+s)!}{(n-1)!(s+1)!}-\frac{(n-1+s)!}{(n-2)!(s+1)!}=\frac{(n+s-1)!(n+s))}{(n-1)!(s+1)!}-\frac{(n-1+s)!(n-1)}{(n-1)!(s+1)!}=$$

$$\frac{(n+s-1)!}{(n-1)!(s)!}=^{s-1}\sum_{n}n$$

Ps: in similair fashion: To figure sums similair to integrating, and if you combine this with the found sum in the question you can easily derive the bernouilli numbers aswell.

$.^s\sum_{n} n^{k+1} =n.^s\sum_{n} n^{k}-(s).^{s+1}\sum_{n} (n-1)^{k} $

Also quickly seen by delta'ing, officially the n-1 should be incorperate into the sum, as upper limit.