1. ## Summation

The question is, how many multiplication and addition operations are required to determine:
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$

And modify the sum to reduce the number of computations.

Are there (n-1) + n(i-1) addition operations (outer loop and inner loop respectively) and n*i multiplication operations?

Also, can it be rewritten as

$
n\sum_{j=1}^{i} a_{i}b_{j}\
$

Thanks.

2. In
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\
$

The number of multiplications is:
$
\sum_{i=1}^{n}\ \sum_{j=1}^{i} 1 = \sum_{i=1}^{n}i = \frac {n(n+1)}{2}
$

$
(\sum_{i=1}^{n} i-1)-1 = \frac {(n-1)(n-1+1)}{2}-1= \frac {n(n-1)}{2}-1= \frac {n^2-n-2)}{2}
$

The way to reduce the number of operations is to notice that $a_{i}$ is common to all the terms after the first sum so we can rewrite as:
$
\sum_{i=1}^{n} a_{i} \sum_{j=1}^{i} b_{j}\
$

Now the number of multiplications is:
$
\sum_{i=1}^{n}1 = n
$

which is less than before.

$
(n-1) + \sum_{j=1}^{n-1} j-1
= (n-1) + \frac {(n-1)(n-1+1)}{2}
= (n-1) + \frac {n(n-1)}{2}
$

$
= \frac{ (2n-2)}{2} + \frac {n(n-1)}{2}
= \frac{ (2n-2) +n^2 - n}{2} = \frac {n^2-n-2)}{2}
$

which is the same as before which makes sense because there are still the same number of terms to be added!