Reindexing Sums

In this warmup, you’ll justify a common algebraic trick used in the proof of several identities in network science.

Note

Reindexing Sums

Let \(S\) be a set and let \(C_1,\ldots,C_k\) be a partition of \(S\) (that is, \(C_i\cap C_j = \emptyset\) for \(i\neq j\) and \(\bigcup_{i=1}^k C_i = S\)). Then for any function \(f:S\to\mathbb{R}\), we have

\[ \begin{aligned} \sum_{s\in S} f(s) = \sum_{i=1}^k \sum_{s\in C_i} f(s). \end{aligned} \]

Part A

Give a short argument explaining why this identity is true.

Part B

Let \(p_K\) be the degree distribution; that is, \(p_K(k)\) gives the proportion of nodes in a graph that have degree \(k\). Consider the following two ways of computing the mean degree of the graph:

\[ \begin{aligned} \langle K \rangle = \frac{1}{n}\sum_{i \in N} k_i = \sum_{k=0}^\infty k p_K(k) \end{aligned} \]

Give a careful argument justifying the equality of the two sums, using the identity from Part A. Please explicitly state what the partition \(C_1,\ldots,C_k\) is in this case, as well as the function \(f\).