# Sigma notation for following nested loop

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$.

• The first time through the $j$ loop you get $\sum_{j=1}^{C_0}{0\choose j-1}$. The second time you get $\sum_{j=1}^{C_1}{1\choose C_0+j-1}$. Care is needed because many of the binomial coefficients will evaluate to 0, but $k$ is still incremented. – almagest May 9 '16 at 8:20

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

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

• I thought out of your first solution. Hoped it could be implemented with no more than just two $\sum$. – Abu Bakar May 13 '16 at 9:44