I'm trying to understand the analysis of **bucket sort** in CLRS. Specifically, **equation 8.2** that states:

$$ E[{n_i^2}] = 2 - \frac{1}{n} $$

To prove, CLRS:

Random variable denoting number of elements that fall into bucket i:

$$ {n_i} $$

An indicator random variable that a given element in the input falls into a particular bucket.

$$ X{_i}{_j} $$

so

$$ {n_i} = \sum_{j=1}^{n}X{_ij} $$

Now, CLRS says to ***expand the square and regroup the terms***:

$$ E[{n_i^2}] = E\left[\left(\sum_{j=1}^{n}X{_ij}\right)^2\right] $$

I can see how the above goes to the next step:

$$ = E\left[\sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{jk}\right]$$

I'm confused as to how the above turns into:

$$ = E\left[\sum_{j=1}^{n}X_{ij} + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{jk}\right] $$

For what it's worth, the **Algorithms in a Nutshell** books has a section on bucket sort that also analyzes why it's 2 - 1/n, and it helps me see things a bit more clearly, but still am unclear about the above. From the AiaN book:

$$ E[n_i^2] = Var[{n_i}]+ E^2[n_i]$$

where

$$ Var[{n_i}] = n * p * (1-p) = n * \frac{1}{n} * \left(1 - \frac{1}{n}\right) = 1 - \frac{1}{n} $$

and

$$ E[{n_i}] = n * p = n * \frac{1}{n} = 1$$

which equals 2 - 1/n