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} $$$$ {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{_ij}\right)^2\right] $$$$ 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_{jk}\right]$$$$ = 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} + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{jk}\right] $$$$ = 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
