4
$\begingroup$

If we had a code segment like this:

int sum = 0;
for(int j = 1; j <= n; j++){
    for(int k = 1; k <= j; k++){
        sum += k;
return sum;

then we could convert it into summation notation to evaluate it:

$$\sum_{j=1}^n \sum_{k=1}^j k = \frac 16 n (n + 1) (n + 2)$$ which is trivial to compute.

However, what if we have something like this? (here $j$ and $k$ increase by an integer more than $1$)

int sum = 0;
for(int j = 1; j <= n; j += 3){
    for(int k = 1; k <= j; k += 2){
        sum += k;
return sum;

With these "jumping summations," is it possible to convert into summation notation? I considered putting, say, $j$ in the form $1+3x$ and $k$ in the form $1+2u$, but then one must manually solve for each the index bounds, which isn't pure enough for me (and I'm not convinced that such an approach would work, anyway).

Is there developed theory on how to approach such summations? I feel like there should be an easy way to convert them into typical summations, but I'm not sure how to do so.

$\endgroup$
3
  • 1
    $\begingroup$ Yes it is possible. A hint could be to think of derivatives and integrals (if you have done some calculus). $\endgroup$ Dec 19, 2017 at 16:29
  • $\begingroup$ I've done some calculus, but I'm not entirely sure how that applies here. Could you please elaborate a bit on this? $\endgroup$
    – actinidia
    Dec 19, 2017 at 16:48
  • $\begingroup$ I don't quite know how to explain it well. Maybe I will be able to formulate it better later. $\endgroup$ Dec 19, 2017 at 17:24

2 Answers 2

2
$\begingroup$

Take the code

int sum = 0;
for (int j=1; j<=n; j += t){
    sum += f(j);
}
return sum;

for some function

float f(int);

The output of this code would be

$$f(1)+f(1+t)+\cdots+f(1+st)=\sum_{j=0}^{s}f\big(jt+1\big)$$

where $s=\max\{\sigma\in\Bbb Z:1+\sigma t\le n\}$. Then $s=\max\{\sigma\in\Bbb Z:\sigma\le (n-1)/t\}=\lfloor (n-1)/t\rfloor$.

Applying this to your code, we get

$$\sum_{j=0}^{\lfloor (n-1)/3\rfloor}\sum_{k=0}^{\lfloor 3j/2\rfloor}(2k+1)=\sum_{j=0}^{\lfloor (n-1)/3\rfloor}(\lfloor 3j/2\rfloor+1)^2$$

This is $$S-T$$ where $$S=1^2+2^2+\cdots+(a+1)^2,$$ $$T=3^2+6^2+\cdots+(3b)^2$$ where $a$ is the half, rounded down, of the greatest multiple of $3$ strictly lesser than $n$, and $3b$ is the greatest multiple of $3$ not greater than $a+1$.

$\endgroup$
1
  • $\begingroup$ Why don't we have $\lfloor (j-1)/2 \rfloor$ as the upper bound of the inner summation? Also, how did you get to the $S - T$ part? I don't see how it follows. $\endgroup$
    – actinidia
    Dec 20, 2017 at 5:04
1
$\begingroup$

Your new version can be written $$\sum_{j=1}^{\lfloor \frac n3\rfloor} \sum_{k=1}^{\lfloor\frac j2\rfloor}(2k-1)=\sum_{j=1}^{\lfloor\frac n3\rfloor}\left \lfloor\frac j2\right \rfloor^2$$ which you can sum the same way.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .