[Math] Sigma notation for following nested loop

algorithmssummationsummation-method

How may the following programming statement be written as summation?

k = 0;
for i = 0 to n-1 {
   for j = 1 to C[i] {
      sum = sum + binom(i,k);
      k++;
   }
}

I started with $$\sum_{i=0}^{n-1}\sum_{j=1}^{C_i} \binom{i}{k}$$ but don't know how to accomodate $k$.

Best Answer

We use the convention that empty sums, i.e. sums with upper limit less than the lower limit are considered to be zero. We also use the convention \begin{align*} \binom{n}{k}=0\qquad\qquad 0\leq n<k \end{align*}

We obtain in accordance with the comment of @almagest

\begin{align*} \sum_{j=1}^{C_0}&\binom{0}{j-1}+\sum_{j=1}^{C_1}\binom{1}{C_0+j-1}+\sum_{j=1}^{C_2}\binom{2}{C_0+C_1+j-1} +\cdots+\sum_{j=1}^{C_{n-1}}\binom{n-1}{\sum_{l=0}^{n-2}C_l+j-1}\\ &\quad=\sum_{i=0}^{n-1}\sum_{j=1}^{C_i}\binom{i}{\sum_{l=0}^{i-1}C_l+j-1} \end{align*}

We can also shift the index $j$ to obtain (by setting $C_{-1}:=0$)

\begin{align*} \sum_{j=0}^{C_0-1}&\binom{0}{j}+\sum_{j=C_0}^{C_0+C_1-1}\binom{1}{j}+\sum_{j=C_0+C_1}^{C_0+C_1+C_2-1}\binom{2}{j} +\cdots+\sum_{j=C_0+C_1+\cdots+C_{n-2}}^{C_0+C_1+\cdots+C_{n-1}-1}\binom{n-1}{j}\\ &\qquad=\sum_{i=0}^{n-1}\sum_{j=\sum_{l=0}^{i-1}C_l}^{\sum_{l=0}^{i}C_l-1}\binom{i}{j} \end{align*}

Related Question