Summation by Parts

Section 4.3 Summation by Parts

Subsection 4.3.1 Integration by parts

\begin{equation} \int u dv = uv - \int v du, \qquad \int_y^x u dv = \left. uv \right|_y^x - \int_y^x v du\text{.}\tag{4.3.1} \end{equation}

Subsection 4.3.2 Summation by parts

Theorem 4.3.1.

Let \((a_n)_{n \geq 1}\) and \((f(n))_{n \geq 1}\) be sequences of complex numbers and let \(1 \leq c \lt b\) be positive integers. For each \(N \in \bbN\text{,}\) let \(A(N) = \sum_{n=1}^N a_n\text{.}\) Then

\begin{equation} \sum_{n=c}^b a_n f(n) = A(b)f(b) - A(c-1)f(c) - \sum_{n=c}^{b-1} A(n)(f(n+1) - f(n))\text{.}\tag{4.3.2} \end{equation}

In this theorem, \(a_n\) plays the role of \(dv\) and \(A(N)\) corresponds to the antiderivative \(v\text{;}\) conversely, \(f(n)\) corresponds to \(u\) and the difference \(f(n+1)-f(n)\) corresponds to the differential \(du\text{.}\) Observe that this is a forward difference. (A backwards difference would be \(f(n)-f(n-1)\text{.}\) Exercise: find a version of summation by parts using backwards differences.)

Observe that

\begin{equation*} \left. A(n)f(n) \right|_c^b \end{equation*}

would be

\begin{equation*} A(b)f(b) - A(c)f(c)\text{,} \end{equation*}

slightly different from the \(A(b)f(b)-A(c-1)f(c)\) appearing in the theorem. Likewise, the sum on the right hand side has bounds \(c \leq n \leq b-1\) instead of \(c \leq n \leq b\text{.}\) So, in contrast to integration by parts, the bounds of summation are slightly different. But then, in the case of integration, if we think of summing rectangles (as in Riemann summation), the difference here is just two rectangles (one at each endpoint), and since the rectangles are “infinitesimally thin”, it doesn’t make a difference to include it or not.

Exercise 4.3.2.

Use summation by parts with Riemann sums to prove integration by parts.

Proof of summation by parts.

Expand the right hand side and cancel terms.

Prev Top Next