Vtgyjfy

Could we solve the multiple summations

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

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

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}
cdotssum_{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}
cdotssum_{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 ,vdotstag{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}
cdotssum_{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}
cdotssum_{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(Kcolor{blue}{-(q-1)z}+1-j_{q-1}right)tag{4}\
&quad=sum_{1leq j_1leqcdotsleq 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+1right)sum_{1leq j_1leqcdotsleq j_{q-1}leq K-(q-1)z}1
-sum_{1leq j_1leqcdotsleq j_{q-1}leq K-(q-1)z}j_{q-1}tag{6}\
&quad=left(K-(q-1)z+1right)binom{K-(q-1)z+q-2)}{q-1}
-sum_{j_{q-1}=1}^{K-(q-1)z}j_{q-1}sum_{1leq j_1leqcdotsleq j_{q-2}leq j_{q-1}}1tag{7}\
&quadcolor{blue}{=left(K-(q-1)z+1right)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_{1leq j_1leqcdotsleq j_nleq 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.