How is summation by parts technique used in this derivation?

Question

In this answer, whuber comments that the technique used in the answer is summation by parts:

The discrete case, assume that $X \ge 0$ takes non-negative integer values. Then we can write the expectation as $$\DeclareMathOperator{\E}{\mathbb{E}} \DeclareMathOperator{\P}{\mathbb{P}} \E X = \sum_{k=0}^\infty k \P(X=k) $$ Now, we will first write this as a double sum, and then change the order of summation. Observe that $k = \sum_{j=0}^{k-1} 1$ (the case $k=0$ gives an upper limit that is smaller than the lower limit, we take that as the empty sum, which is zero). This gives $$ \E X = \sum_{k=0}^\infty \sum_{j=0}^{k-1} 1 \cdot \P(X=k) $$ Now, in this double sum we sum first on $j$, which clearly goes to $\infty$. Observe that in the inner summation the indices satisfy the inequality $$ 0 \le j \le k-1 $$ Solving that for $k$ gives $ k \ge j+1$, which then gives the limits of summation in the new inner sum: $$ \E X = \sum_{j=0}^\infty \sum_{k=j+1}^\infty \P(X=k) = \sum_{j=0}^\infty \P(X > j) $$ which is the result. The continuous case is similar.

I went to the wikipedia to try to understand his comment but I do not get it.

Suppose $\{f_k\}$ and $\{g_k\}$ are two sequences. Then,

$$ \sum_{k=m}^{n} f_k (g_{k+1} - g_k) = (f_{n+1} g_{n+1} - f_m g_m) - \sum_{k=m}^{n} g_{k+1} (f_{k+1} - f_k). $$

In what way is rearranging the sums related to summation by parts?

Answer 1

Ok since whuber commented, I decided to look back into it and figured it out.

I think the following expression from wikipedia makes it easier to understand: $$ \sum_{k=0}^n f_k g_k = f_0 \sum_{k=0}^n g_k + \sum_{j=0}^{n-1} (f_{j+1} - f_j) \sum_{k=j+1}^n g_k. $$

Also as whuber hinted:

$$ f_k = \sum_{i'=0}^{k-1} 1 . $$

So the first part of the definition is $$ \sum_{k=0}^n f_k g_k = \sum_{k=0}^{\infty}\left ( P(X=k) \times \sum_{i'=0}^{k-1} 1 \right) $$

So the equivalent is,

$$ f_0 \sum_{k=0}^n g_k + \sum_{j=0}^{n-1} (f_{j+1} - f_j) \sum_{k=j+1}^n g_k =\sum_{i'=0}^{0} 1 \times \sum_{k=0}^{\infty} P(X=k) + \sum_{j=0}^{\infty} \left(\sum_{i'=0}^{j+1} 1 - \sum_{i''=0}^{j} 1 \right) \sum_{k=j+1}^n P(X=k) $$

$$ = 0 + \sum_{j=0}^{\infty} 1 \times \sum_{k=j+1}^{\infty} P(X>j) = \sum_{j=0}^{\infty} P(X>j) = \sum_{j=0}^{\infty} 1 - P(X<j). $$