1

Could we solve the multiple summations

$N = \sum\limits_{{j_1} = 1}^{K - \left( {q - 1} \right)z} {\sum\limits_{{j_2} = {j_1} + z}^{K - \left( {q - 2} \right)z} { \cdots \sum\limits_{{j_k} = {j_{k - 1}} + z}^{K - \left( {q - k} \right)z} \cdots \sum\limits_{{j_{q - 1}} = {j_{q - 2}} + z}^{K - z} {\left( {K - z + 1 - {j_{q - 1}}} \right)} } }$,

where $K,z,q$ are positive integers.

Hui Zhao
  • 75

1 Answers1

0

We can simplify the multiple sum as follows \begin{align*} &\color{blue}{\sum_{j_1=1}^{K-(q-1)z}\,\sum_{j_2=j_1+z}^{K-(q-2)z}\,\sum_{j_3=j_2+z}^{K-(q-3)z} \cdots\sum_{j_{q-2}=j_{q-3}+z}^{K-2z}\,\sum_{j_{q-1}=j_{q-2}+z}^{K-z}\left(K-z+1-j_{q-1}\right)}\\ &\quad=\sum_{j_1=1}^{K-(q-1)z}\,\sum_{\color{blue}{j_2=j_1}}^{\color{blue}{K-(q-1)z}}\,\sum_{\color{blue}{j_3=j_2+2z}}^{K-(q-3)z} \cdots\sum_{j_{q-2}=j_{q-3}+z}^{K-2z}\,\sum_{j_{q-1}=j_{q-2}+z}^{K-z}\left(K-z+1-j_{q-1}\right)\tag{1}\\ &\quad\ \,\vdots\tag{2}\\ &\quad=\sum_{j_1=1}^{K-(q-1)z}\,\sum_{j_2=j_1}^{K-(q-1)z}\,\sum_{j_3=j_2}^{K-(q-1)z} \cdots\sum_{\color{blue}{j_{q-2}=j_{q-3}}}^{\color{blue}{K-(q-1)z}}\,\sum_{\color{blue}{j_{q-1}=j_{q-2}+(q-2)z}}^{K-z}\left(K-z+1-j_{q-1}\right)\tag{3}\\ &\quad=\sum_{j_1=1}^{K-(q-1)z}\,\sum_{j_2=j_1}^{K-(q-1)z} \cdots\sum_{j_{q-2}=j_{q-3}}^{K-(q-1)z}\,\sum_{\color{blue}{j_{q-1}=j_{q-2}}}^{\color{blue}{K-(q-1)z}}\left(K\color{blue}{-(q-1)z}+1-j_{q-1}\right)\tag{4}\\ &\quad=\sum_{1\leq j_1\leq\cdots\leq j_{q-1}\leq K-(q-1)z}\left(K-(q-1)z+1-j_{q-1}\right)\tag{5}\\ &\quad=\left(K-(q-1)z+1\right)\sum_{1\leq j_1\leq\cdots\leq j_{q-1}\leq K-(q-1)z}1 -\sum_{1\leq j_1\leq\cdots\leq j_{q-1}\leq K-(q-1)z}j_{q-1}\tag{6}\\ &\quad=\left(K-(q-1)z+1\right)\binom{K-(q-1)z+q-2)}{q-1} -\sum_{j_{q-1}=1}^{K-(q-1)z}j_{q-1}\sum_{1\leq j_1\leq\cdots\leq j_{q-2}\leq j_{q-1}}1\tag{7}\\ &\quad\color{blue}{=\left(K-(q-1)z+1\right)\binom{K-(q-1)z+q-2)}{q-1} -\sum_{j_{q-1}=1}^{K-(q-1)z}j_{q-1}\binom{j_{q-1}+q-3}{q-2}}\tag{8}\\ \end{align*}

Comment:

  • In (1) we shift the index $j_2$ by $z$ to start with $j_2=1$.

  • In (2) we successively shift $j_3$ by $2z$, $j_4$ by $3z$ up to $j_{q-3}$ by $(q-2)z$ in order start from $j_k=j_{k-1}$ with upper limits $K-(q-1)z$.

  • In (3) we shift the index $j_{q-2}$ by $(q-3)z$ to start with $j_{q-2}=j_{q-3}$.

  • In (4) we finally shift the index $j_{q-1}$ by $(q-2)$ to start with $j_{q-1}=j_{q-2}$ and to complete the first step of simplification.

  • In (5) we write the index region more conveniently.

  • In (6) we split the sum and factor out the constant $K-(q-1)z+1$ from the left-hand sum.

  • In (7) we observe the left-hand sum is the number of ordered $q-1$-tuples with repetition from a set with $K-(q-1)z$ elements following the formula \begin{align*} \sum_{1\leq j_1\leq\cdots\leq j_n\leq K}1=\binom{n+K-1}{n}\tag{9} \end{align*} We rearrange the right-hand sum in (6) by summing up at first over $j_{q-1}$ so that we can factor out $j_{q-1}$ leaving a multiple sum with a structure analogously to the left-hand sum in (6).

  • In (8) we finally apply (9) again.

Markus Scheuer
  • 108,315