How to evaluate $\sum_{ i}\sum_{ j}\sum_{ k}\sum_{ l} 2 \ \ where \ \ 1\le i \le j \le k \le l\le n $?

Question

Any hint on how to tackle these types of problem?

$$\sum_{ i}\sum_{ j}\sum_{ k}\sum_{ l} 2 \ \ where \ \ 1\le i \le j \le k \le l\le n $$

Answer 1

In how many ways can we pick $i,j,k,l\in[1,n]$ such that $i\leq j\leq k\leq l$?

By setting $a=i-1, b=j-i, c=k-j, d=l-k, e=n-l$ we have that the answer is given by the number of ways for writing $n-1$ as $a+b+c+d+e$ with $a,b,c,d,e\in\mathbb{N}$, i.e. by the coefficient of $x^{n-1}$ in $(1+x+x^2+x^3+\ldots)^5 = \frac{1}{(1-x)^5}$. By stars and bars

$$ \frac{1}{(1-x)^5} = \sum_{m\geq 0}\binom{m+4}{4}x^m $$ hence the answer to OP's question is $2\binom{n+3}{4}=\color{blue}{\frac{n(n+1)(n+2)(n+3)}{12}}$.

^{I am assuming $0\in\mathbb{N}$ as I am used to.}

Answer 2

A lot of problem/exercise one encounter in school can be attacked by pattern recognition. One work out simpler version of the problem, guess what the answer should look like and use this as a hint to figure out what steps to follow.

Let use this as an example to illustrate this approach. It is clear the factor $2$ in the summand is a distraction, we can move it outside all the sum. Let's work out what the shorter form of the sum should look like first.

Summing over a single index is trivial, we have $$\sum_{1 \le i \le n} 1 = n$$

Summing over two indices is not that hard, we have $$\sum_{1\le i \le j \le n} 1 = \sum_{j=1}^n \sum_{1 \le i \le j} 1 = \sum_{j=1}^n j = \frac{n(n+1)}{2}$$

Summing over three indices starts to become tricky, we first obtain $$\sum_{1\le i \le j \le k \le n} 1 = \sum_{k=1}^n \sum_{1 \le i \le j \le k} 1 = \sum_{k=1}^n \frac{k(k+1)}{2}$$

The last sum is a problem. We can break it as a sum over $k^2$ and $k$, lookup the formula for a sum of $k^2$. Combine all the mess and simplify. The end results looks surprisely simple and looks similar to what we have for two indices.

$$\sum_{1\le i \le j \le k \le n} 1 = \frac{n(n+1)(n+2)}{3!}$$

One may wonder is there a way to derive this directly to avoid the same mess for sums for more indices. The answer is yes, we have

$$\sum_{k=1}^n \frac{k(k+1)}{2} = \sum_{k=1}^{n}\frac{(\color{red}{k+2})-(\color{blue}{k-1})}{3}\frac{k(k+1)}{2} = \sum_{k=1}^{n}\frac{k(k+1)(\color{red}{k+2}) - (\color{blue}{k-1})k(k+1)}{3!} $$ The sum can be transformed to a telescoping one! With this discovery, the sum for four indices become a piece of cake. We have

$$\begin{align} \sum_{1\le i \le j \le k \le \ell \le n} 1 &= \sum_{\ell=1}^n \sum_{1 \le i \le j \le k \le \ell} 1 = \sum_{\ell=1}^n \frac{\ell(\ell+1)(\ell+2)}{3!}\\ &= \sum_{\ell=1}^n \frac{\ell(\ell+1)(\ell+2)(\ell+3) - (\ell-1)\ell(\ell+1)(\ell+2)}{4!}\\ &= \frac{n(n+1)(n+2)(n+3)}{4!}\end{align}$$

The desired sum is simply twice of this:

$$\sum_{1\le i \le j \le k \le \ell \le n} 1 = 2\binom{n+3}{4} = \frac{n(n+1)(n+2)(n+3)}{12}$$

Answer 3

$$\begin{align} \sum_{1\le i\le j\le k\le l\le n} &=\;\;\;\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^n\sum_{l=k}^n 2\\ &=\;\;\;\sum_{l=1}^n\sum_{k=1}^l\sum_{j=1}^k\sum_{i=1}^j 2\\ &=2\sum_{l=1}^n\sum_{k=1}^l\sum_{j=1}^k\sum_{i=1}^j \binom {i-1}0\\ &=2\sum_{l=1}^n\sum_{k=1}^l\sum_{j=1}^k\binom {j+0}1\\ &=2\sum_{l=1}^n\sum_{k=1}^l\binom {k+1}2\\ &=2\sum_{l=1}^n\binom {l+2}3\\ &=\color{red}{2\binom {n+3}4}\end{align}$$