I am having trouble solving the following nested summation:

$$\sum_{i=0}^{n-1} \sum_{j=i}^{n-1}p(A_i)p(B_j) $$

where $p(A_i) = \frac{1}{n}$, and $n$ is a constant (length of an array). Same goes for $p(B_i) = \frac{1}{n}$.

I tried rewriting it into this form:

$$\sum_{i=0}^{n-1} \left(p(A_i)\sum_{j=i}^{n-1}p(B_j)\right) $$ as $p(A_i)$ doesn't depend on the index j, however I still have no idea what to do with the inner sum.

  • $\begingroup$ @Casteels I edited the question so, the variable $n$ better corresponds to the size of an array as we iterate the sum from $0$ to $n-1$ $\endgroup$ – John Smith Oct 26 '13 at 10:57

First, $\sum_{j=i}^{n-1}p(B_j)$ means you're adding up $n-i$ $\frac{1}{n}$'s, so this sum becomes just $\frac{n-i}{n}$. So your desired sum is \begin{eqnarray*} \sum_{i=0}^{n-1}\frac{n-i}{n^2} &=& \frac{1}{n^2}\sum_{i=0}^{n-1}(n-i)\\ &=& \frac{1}{n^2}\sum_{i=0}^{n-1}n - \frac{1}{n^2}\sum_{i=0}^{n-1}i\\ &=&\frac{1}{n^2}n(n)-\frac{1}{n^2}\frac{(n-1)n}{2} \\ &=& 1-\frac{n-1}{2n} \\ &=&\frac{1}{2}+\frac{1}{2n}.\end{eqnarray*}

PS, A slightly quicker way: In the first step, notice $\sum_{i=0}^{n-1}(n-i)=\sum_{i=1}^{n}i = \frac{n(n+1)}{2}$...

  • $\begingroup$ Brilliant! Thank you so much :) $\endgroup$ – John Smith Oct 26 '13 at 11:40

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.