# Intuition behind sums of sums of whole numbers

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?

• It's interesting you expressed it as $\frac 12 n^2 +\frac 12n$ rather than $\frac{n(n+1)}2$ and that as ${n+1 \choose n-1}$ rather than as ${n+1 \choose 2}$ and you chose to express $N_2(n)$ as ${n+2 \choose n-1}$ rather than as ${n+2 \choose 3}$. As for intuition I suggest you read up on "stars and bars". $1+2+... + n = n\cdot (avg 1...n) = n\cdot \frac {n+1}2$ is one bit of intuition. And ${n+1\choose 2}=\sum k$ intuition is this: imagine you have $n+1$ spaces and you need fill two of them with a bars and the rest with stars. The way to do that is ${n\choose 2}$. Now if you count them TBC Aug 11, 2020 at 23:06
• If you count them, if you put the second bar at position $k$ and the first bar at a position $j< k$. if $k = 2$ then there is $1$ choice for $j$.. If $k =3$ there are $2$ choices for $j$ if $k=4$ there are $3$ choices for $j$ and so on up to if $k=n+1$ there are $n$ choices for $j$. So if you add these up there are $1+2+3+4+.... + n$ ways to choose $2$ from $n+1$. So $\frac {n!}{2!(n-1)!} = \frac {(n+1)n}2 = {n+1 \choose 2}=1+2+.... + n = n\times avg (1....n) = n\times \frac {n+1}2 = \frac {n(n+1)}2$. Aug 11, 2020 at 23:11
• en.wikipedia.org/wiki/Hockey-stick_identity may be worth a look. Aug 11, 2020 at 23:14
• What does $k$ represent here? It doesn't make enough idea to me. Aug 12, 2020 at 9:40
• Just came across a hint towards "Conway/Guy: hyper-harmonic numbers". They handle this very generally. Dec 23, 2020 at 1:53

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}$$.

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.

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.)

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)

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.

• Hi Gerben, I've seen this in a couple of postings of you now and I don't know whether you really want to display the dot at your superposed $s$ for the iteration-index. If not, then you can the latex-/mathjax blank for this, for instance \;^s giving $\;^2\sum_{k=1}^\infty \cdots$. Even more, at the (big) sum-symbol, it might look better with \;^{\;^2} giving $\;^{\;^2}\sum_{k=1}^\infty \cdots$ Dec 25, 2020 at 19:28
• Thanks! That does look better :) the dot wasn't intended but just to make sure it's not seen as a power of the thing before. Dec 26, 2020 at 8:35