Evaluate $\sum\limits_{1 \le j\le k\le n} jk $ I am trying to solve an exercise from Concrete Mathematics but I seem to be stuck on the sum $$\sum_{1 \le j\le k\le n} jk $$ How to proceed? I have tried using Iverson's bracket condition like 
$$ [1\le j\le k\le n] = [1\le j \le n][j\le k \le n] $$
but I am not sure how to write the sum as multiple sums.
 A: Consider the following identity, with its obvious meaning:
$$
\left(\sum_i\right)^2=
\sum_{i,j}=\sum_{i<j}+\sum_{i=j}+\sum_{j>i}=2\sum_{i<j}+\sum_{i=j}.
$$
Therefore
$$
\frac{n^2(n+1)^2}{4}=2\sum_{i<j}+\frac{n(n+1)(2n+1)}{6}.
$$
We conclude that
\begin{align*}
\sum_{i\le j}=\sum_{i=j}+\sum_{i<j}&=\frac{n(n+1)(2n+1)}{6}+\frac{1}{2}\left(\frac{n^2(n+1)^2}{4}-\frac{n(n+1)(2n+1)}{6}\right) \\\
&=\frac{n(n+1)(2n+1)}{12}+\frac{n^2(n+1)^2}{8}.
\end{align*}
A: HINT:
Write
$$\sum_{1 \le j\le k\le n} jk $$
as 
$$\sum_{j=1}^{n}\left[\sum_{k=j}^{n} jk \right] = \sum_{j=1}^{n}j\left[\sum_{k=j}^{n} k \right] = \sum_{j=1}^{n}j\cdot\left(\frac{j+n}{2}\cdot(n-j+1)\right)$$
From the arithmetic sums.
This sum is, in turn, decomposable in 4 simpler sums. Can you take it from here?
A: Break the sum over values of $k$ from $1$ to $n$ and note that $1 \le j \le k$.
$$S = \sum_{1 \le j\le k\le n} jk = 1 \sum_{j=1}^1 j \ + 2 \sum_{j=1}^2 j \ + 3 \sum_{j=1}^3 j \ ....+ \ n \sum_{j=1}^n j \ $$
The general term of the above sequence is $ \ \  T_n = n \frac{n(n+1)}{2}$.
Simplifying $T_n$ we get,
$$T_n = \frac{n^3 + n^2}{2}$$
And now $S_n = \sum T_n =\frac{ \sum n^3 + \sum n^2}{2}$
Use the expressions of $\sum n^2$ and $\sum n^3$ and simplify to get your required sum. 
A: An alternative is to set $j-1=a, k-j=b, n-k=c$. Then we are looking for
$$ S(n)=\sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}(a+1)(a+b+1)=\sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}(1+2a+b+a^2+ab) $$
where
$$ \sum_{d\geq 0}x^d = \frac{1}{1-x},\qquad \sum_{d\geq 0}dx^d = \frac{x}{(1-x)^2},\qquad \sum_{d\geq 0}d^2 x^d = \frac{x(1+x)}{(1-x)^3} $$
and
$$ \sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}\!\!\!1 = [x^{n-1}]\frac{1}{(1-x)^3},\qquad \sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}a=[x^{n-1}]\frac{x}{(1-x)^4} $$
$$ \sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}\!\!\!a^2 = [x^{n-1}]\frac{x(1+x)}{(1-x)^5},\qquad \sum_{\substack{a+b+c=n-1\\a,b,c\geq 0}}ab=[x^{n-1}]\frac{x^2}{(1-x)^5} $$
so
$$ S(n) = [x^{n-1}]\left(\frac{1}{(1-x)^3}+\frac{3x}{(1-x)^4}+\frac{x(1+x)}{(1-x)^5}+\frac{x^2}{(1-x)^5}\right)$$
or
$$ S(n) = [x^{n-1}]\frac{2x+1}{(1-x)^5}=\binom{n+3}{4}+2\binom{n+2}{4}=\color{red}{\frac{n(n+1)(n+2)(3n+1)}{24}}. $$

An interesting and more practical way is to prove first that $S(n)$ is a fourth-degree polynomial in the $n$ variable, then find its coefficients through Lagrange interpolation, once computed $S(1),S(2),S(3),S(4),S(5)$.
A: Hint:
Write it as a double sum:
$$\sum_{j=1}^n\sum_{k=j}^njk=\sum_{j=1}^n\left(j\sum_{k=j}^nk\right)=\sum_{j=1}^nj\frac{(j+n)(n-j+1)}2=\frac12\sum_{j=1}^n(j(n^2+n)+j^2-j^3).$$
The rest is a simple application of the Faulhaber formulas.
