Trying to understand CLRS bucket sort analysis

Question

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{_i}{_j} $$

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

$$ E[{n_i^2}] = E\left[\left(\sum_{j=1}^{n}X{_i}{_j}\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_{ik}\right]$$

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

$$ = E\left[\sum_{j=1}^{n}X_{ij}^2 + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{ik}\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

Answer 1

You are asking why

$\qquad\displaystyle \sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik} \quad=\quad \sum_{j=1}^{n}X_{ij}^2 + \sum_{j = 1}^{n}\sum_{1 \leq k \leq n,\\ k \neq j}X_{ij}X_{ik}$

holds (in expectation, but that's irrelevant for this; it might not always be, though!).

Note that the left-hand side and the second summand on the right-hand site are identical except for the $k \neq j$ constraint. That is, the difference between the two terms is exactly

$\qquad\displaystyle \sum_{j=1}^n \sum_{1 \leq k \leq n,\\k=j} X_{ij}X_{ik} \quad=\quad \sum_{j=1}^n X_{ij}X_{ij} \quad=\quad \sum_{j=1}^{n}X_{ij}^2$.

No deep insight here, just basic manipulation of sums.