Summation by Parts
An important technique of calculus is integration by parts:
∫b
a u(x)v'(x)dx = u(b)v(b) − u(a)v(a) − ∫b
a u'(x)v(x)dx
This is useful, obviously, when u'(x)v(x) is easier to integrate than
u(x)v'(x), e.g., if u(x) = x and v(x) = ex.
An analogous technique, called summation by parts, works for
sums. One version of the summation by parts formula is:
Σb
i=a+1 ui (vi − vi−1)
= ubvb − uava − Σb
i=a+1 (ui − ui−1)vi −1
Example: Find Σn
i=1 i2i.
Set a = 0, b = n, ui = i, and vi = 2i+1.
Then ui − ui−1 = 1, vi − vi−1 = 2i+1 − 2i = 2i , and
Σn
i=1 i2i = Σb
i=a+1 ui (vi − vi−1)
= ubvb − uava − Σb
i=a+1 (ui − ui−1)vi −1
= n2n+1 − 0⋅21 − Σn
i=1 1⋅2i
= n2n+1 − (2n+1 − 2)
= (n − 1)2n+1 + 2