Concrete Mathematics Warmup 4: Expanding a Triple Sum

73 Views Asked by At

I am trying to solve this, rather simple, triple sum, by expanding it and first summing with respect to the index k.

$$ \sum_{1 \leq i < j < k \leq 4} a_{ijk} $$

I didn't quite get the trick to expand multiple sums but I attempted anyway. I used the Iverson notation explained in the book.

$$ \sum_{i,j,k} a_{ijk}\hspace{0,1cm} [ 3 \leq k\leq 4]\hspace{0,1cm} [ 2\leq j\leq 3]\hspace{0,1cm} [1\leq i\leq 2] $$

But this is clearly wrong since i need to add the condition that $$i\neq j \wedge j\neq k$$

I can't go further. Can someone explain how to proceed?

2

There are 2 best solutions below

2
On BEST ANSWER

You can easily reason out that the only combinations of numbers satisfying $1\leqslant i <j<k\leqslant4$ are $123$, $124$, $134$, and $234$. Thus your sum equals $$a_{123}+a_{124}+a_{134}+a_{234}.$$


Alternatively, working with the Iverson bracket, we have the following in the general case:

\begin{align*} \sum_{1\leqslant i<j<k\leqslant n}a_{ijk}&=\sum_k\sum_j\sum_i a_{ijk}[1\leqslant i][i<j][j<k][k\leqslant n]\\ &=\sum_k[k\leqslant n]\sum_j[j<k]\sum_i a_{ijk}[1\leqslant i][i<j]\\ &=\sum_{k\leqslant n}\sum_{j<k}\sum_{1\leqslant i<j} a_{ijk}, \end{align*} or written differently, $$\sum_{k=3}^n\sum_{j=2}^{k-1}\sum_{i=1}^{j-1} a_{ijk},$$ where the cases for $k=1,2$ and $j=1$ are excluded because of the restriction on the following subscripts (when $k=1$, there are no $j<k$; similarly when $k=2$, we can only have $j=1$, but then there are no $i<j$).

Expanding this out with $n=4$: \begin{align*} \sum_{k=3}^4\sum_{j=2}^{k-1}\sum_{i=1}^{j-1} a_{ijk} &= \sum_{j=2}^{2}\sum_{i=1}^{j-1} a_{ij3} +\sum_{j=2}^{3}\sum_{i=1}^{j-1} a_{ij4}\\ &= \sum_{i=1}^{1} a_{i23} + \sum_{i=1}^{1} a_{i24} +\sum_{i=1}^{2} a_{i34}\\ &= a_{123} + a_{124} + a_{134} + a_{234}. \end{align*}

0
On

Let $ n\in\mathbb{N}^{*}\setminus\left\lbrace 1,2\right\rbrace $, then we have the following :

$$ \sum_{1\leq i<j<k\leq n}{a_{ijk}}=\sum_{k=3}^{n}{\sum_{j=2}^{k-1}{\sum_{i=1}^{j-1}{a_{ijk}}}} $$