Why does this equivalence of sums hold? I have to prove that a function is a pdf. In the master solution they state the below equivalence in the proof. What rules are applied to get from the left side to the right side?
$$C\sum_{k=2}^{\infty} \sum_{j=1}^{k-1}\left(\frac{1}{2}\right)^{k}=C \sum_{j=1}^{\infty} \sum_{k=j+1}^{\infty}\left(\frac{1}{2}\right)^{k}$$
 A: The most straightforward way to prove this equation has nothing to do with the actual summand: if you replace $(1/2)^k$ by anything else, the equation is also true (with an appropriate convergence hypothesis). It just comes down to an equality of index sets.
To see this intuitively, note that in the Cartesian coordinate plane, with horizontal axis labelled $j$ and vertical axis labelled $k$, the index sets on both sides of the equation are equal to the set of integer lattice points in the open $1^{\text{st}}$ quadrant on or above the line $k=j+1$.
Guided by that intuition, you can probably see quite directly that for any $(j,k) \in \mathbb N \times \mathbb N$,
\begin{align*}
& \quad \bigl( 2 \le k \quad\text{and}\quad  1 \le j \le k-1 \bigl)\\
\text{if and only if} & \quad \bigl( j \ge 1 \quad\text{and}\quad  k \ge 2 \quad\text{and}\quad k \ge j+1 \bigr) \\
\text{if and only if} & \quad \bigl( 1 \le j \quad\text{and}\quad  j+1 \le k \bigr)
\end{align*}
A: The equivalence can be easily shown by double counting according to the following scheme

indeed

*

*$\sum_{k=2}^{\infty} \sum_{j=1}^{k-1}\left(\frac{1}{2}\right)^{k}$ is the sum column by column

*$ \sum_{j=1}^{\infty} \sum_{k=j+1}^{\infty}\left(\frac{1}{2}\right)^{k}$ is the sum row by row

A: Using geometric series, for the inner sum we have $\sum_{j=1}^{k-1}\left(\frac{1}{2}\right)^k=\frac{k-1}{2^k}$. Now inserting this result into the outer sum, we get $\sum _{k=2}^R \frac{k-1}{2^k}=1-\frac{R+1}{2^R}$.
Putting this together, we obtain for the left side (by using the limit $R$ instead of infinity):
$$\sum_{k=2}^{R}\sum_{j=1}^{k-1}\left(\frac{1}{2}\right)^k=1-\frac{R+1}{2^R}$$
So what is happening on the right side? For the inner sum we have $\sum _{k=j+1}^R \left(\frac{1}{2}\right)^k=\frac{1}{2^j}-\frac{1}{2^R}$. Let us insert this result into the outer sum and we obtain as well $\sum _{j=1}^R \left(\frac{1}{2^j}-\frac{1}{2^R}\right)=1-\frac{R+1}{2^R}$.
Therefore, when replacing on the right side in both sums infinity with $R$, you get as well:
$$\sum_{j=1}^{R}\sum_{k=j+1}^{R}\left(\frac{1}{2}\right)^k=1-\frac{R+1}{2^R}$$
Hence we can conclude $C\left(1-\frac{R+1}{2^R}\right)=C\left(1-\frac{R+1}{2^R}\right)$ which is true.
