Probability, Random Variables, and Random Processes: Theory and Signal Processing Applications

E.10 SUMMATION BY PARTS

Summation by parts is a technique for evaluating a finite sum of sequences that is analogous to integration by parts used for continuous functions.

Lemma E.1. For sequences x[k] and y[k]:

(E.66)

Proof. This expression is verified by bringing the sums to the left-hand side and combining them to cancel the x[k]y[k] terms:

(E.67)

The right-hand side follows because all other terms in the sum cancel.

Note that other forms are possible, such as

(E.68)

Defining the difference sequences and , (E.68) can be written as

(E.69)

This form resembles integration by parts:

(E.70)

which has been written using Riemann–Stieltjes integrals (see Appendix D).

Example E.3. Summation by parts can be used to verify the finite sum formula in (E.34). Letting x[k] = k and y[k] = xk