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

Question

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.

Answer 1

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