1. Summation

The question is, how many multiplication and addition operations are required to determine:
$\displaystyle \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

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

Thanks.

2. In
$\displaystyle \sum_{i=1}^{n}\ \sum_{j=1}^{i} a_{i}b_{j}\$
The number of multiplications is:
$\displaystyle \sum_{i=1}^{n}\ \sum_{j=1}^{i} 1 = \sum_{i=1}^{n}i = \frac {n(n+1)}{2}$
$\displaystyle (\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 $\displaystyle a_{i}$ is common to all the terms after the first sum so we can rewrite as:
$\displaystyle \sum_{i=1}^{n} a_{i} \sum_{j=1}^{i} b_{j}\$

Now the number of multiplications is:
$\displaystyle \sum_{i=1}^{n}1 = n$
which is less than before.

$\displaystyle (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}$
$\displaystyle = \frac{ (2n-2)}{2} + \frac {n(n-1)}{2} = \frac{ (2n-2) +n^2 - n}{2} = \frac {n^2-n-2)}{2}$