1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – almagest May 9 '16 at 8:20
1
$\begingroup$

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*}

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.