Before explaining the problem, I'll try to give some context, the context only serves to understand where the problem fits. The real question is purely algebraic and concerns an equality that I cannot justify. The question is therefore inserted in a precise point of the proof: In the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. In chapter 8, when dealing with the cost analysis of the BUCKET-SORT algorithm, the following statements are made:
To analyze the cost of the calls to insertion sort, let $n_i$ be the random variable denoting the number of elements placed in bucket B[i]. Since insertion sort runs in quadratic time (see Section 2.2), the running time of bucket sort is
$T(n) = Θ(n)+\sum_{i=0}^{n-1}{O(n_i^2)} $
We now analyze the average-case running time of bucket sort, by computing the expected value of the running time, where we take the expectation over the input distribution. Taking expectations of both sides and using linearity of expectation, we have
$$E[T(n)] = E[ Θ(n)+\sum_{i=0}^{n-1}{O(n_i^2)} ] \overset{\text{(by linearity of expectation)}}{=} Θ(n)+\sum_{i=0}^{n-1}{E[O(n_i^2)]} = Θ(n)+\sum_{i=0}^{n-1}{O(E[n_i^2])} $$
We claim that $$E[n_i^2] = 2 -\frac{1}{n} \text{ this is the equation we want to prove, which in the book is denoted by(8.2)}$$ for i = $0,1,...,n$. It is no surprise that each bucket i has the same value of $E[n_i^2]$, since each value in the input array A is equally likely to fall in any bucket. To prove equation (8.2), we define indicator random variables
$X_{ij} = I({A[j] \text{ falls in bucket i }})$
for $i = 0,1,...,n-1$ and $j = 1,2,...n$. Thus,
$n_i = \sum_{j=i}^n{X_{ij}}$
To compute $E[n_i^2]$, we expand the square and regroup terms:
$E[n_i^2] = E[( \sum_{j=1}^n{X_{ij}} )^2] = E[\sum_{j=1}^n\sum_{k=1}^n{X_{ij}X_{ik}}] \overset{\text{(How is this equality algebraically justified?)}}{=} E[\sum_{j=1}^n{X_{ij}^2}+\sum_{1≤j≤n}\sum_{1≤k≤n, k≠j}{X_{ij}X_{ik}}] \overset{\text{(equation8.3)}}{=} \sum_{j=1}^n{E[X_{ij}^2]}+\sum_{1≤j≤n}\sum_{1≤k≤n, k≠j}{E[X_{ij}X_{ik}]}$
where the last line follows by linearity of expectation. We evaluate the two summations separately. Indicator random variable $X_{ij}$ is 1 with probability 1=n and 0 otherwise, and therefore
$E[x_{ij}^2] = 1^2\frac{1}{n} + 0^2 (1-\frac{1}{n}) = \frac{1}{n}$
When $k≠j$, the values $X_{ij}$ and $X_{ik}$ are independent, and hence
$E[X_{ij}X_{ik}] = E[X_{ij}] E[X_{ik}] = \frac{1}{n}\frac{1}{n} = \frac{1}{n^2}$
Substituting these two expected values in equation (8.3), we obtain
$E[n_i^2] = \sum_{j=1}^n\frac{1}{n}+\sum_{1≤j≤n}\sum_{1≤k≤n, k≠j}{\frac{1}{n^2}} = n\frac{1}{n} + n(n-1)\frac{1}{n^2} = 1+ \frac{n-1}{n} = 2-\frac{1}{n}$
which proves equation (8.2).