Summation By Parts

Summation by parts is analogous to integration by parts.

Consider the two sequences \({ \left\{ { a }_{ n } \right\} }_{ n=1 }^{ \infty }\) and \({ \left\{ { b }_{ n } \right\} }_{ n=1 }^{ \infty }\). Let \(\displaystyle { S }_{ N }=\sum _{ n=1 }^{ N }{ { a }_{ n } } \) be the \(n^\text{th}\) partial sum. Then for \(0 \le m \le n\) we have:

\[\sum _{ k=m }^{ n }{ { a }_{k }{ b }_{k } } =\left[ { S }_{ n }{ b }_{ n }-{ S }_{ m-1 }{ b }_{ m } \right] +\sum _{ k=m }^{ n-1 }{ \left[ { S }_{ k }\left( { b }_{ k }-{ b }_{ k+1 } \right) \right] } \]

The summation can be rearranged to

\[ \begin{eqnarray} \sum_{k=m}^n a_k b_k &=& \sum_{k=m}^n [ (S_k - S_{k-1}) b_k ] \\ &=& \sum_{k=m}^n S_k b_k - \sum_{k=m}^n S_{k-1} b_k \\ &=& \sum_{k=m}^n S_k b_k - \sum_{k=m-1}^{n-1} S_{k} b_{k+1} \\ &=&\begin{array} {c} \left( S_m b_m + S_{m+1} b_{m+1}+ S_{m+2} b_{m+2} + \cdots +\color{purple}{ S_n b_n} \right) \\ - \\ \left( \color{purple}{S_{m-1} b_m} + S_{m} b_{m+1} + S_{m+1} b_{m+2} + \cdots + {S_{n-1} b_n} \right) \end{array} \\ &=& [S_n b_n - S_{m-1} b_m ] + S_m (b_m - b_{m+1}) + S_{m+1} (b_{m+1} - b_{m+2}) + \cdots + S_{n-1} (b_{n-1} - b_n) \\ &=&[S_n b_n - S_{m-1} b_m ] + \sum_{k=1}^{n-1} [ S_k (b_k - b_{k+1}) ] \end{eqnarray} \]

Find \(\displaystyle \sum _{ k=1 }^{ n }{ k{ 2 }^{ k } } \).

---

This sum can be solved using arithmetic-geometric progression, but solving it via summation by parts is so much more fun!

First, we let \(a_k = 2^k\) and \(b_k = k \). Then, the partial sum \(S_n = \sum_{k=1}^n a_k \) can be found using the geometric progression sum, \(S_n = 2^{n+1} - 2 \). And \(b_k - b_{k+1} = k - (k+1) = -1 \). Lastly, by definition, \(S_0 = \sum_{k=1}^0 a_k= 0 \).

Plugging everything into the formula gives

\[\begin{eqnarray} \require{cancel} \sum _{ k=1 }^{ n }{ k{ 2 }^{ k } } &=& \sum_{k=1}^n a_k b_k \\ &= & S_n b_n - \cancelto0{S_0 b_1} + \sum_{k=1}^{n-1} \left [ S_k \cancelto{-1}{(b_k - b_{k+1} )} \right ] \\ &= & n(2^{n+1} - 2) - \sum_{k=1}^{n-1} S_k \\ &= & n(2^{n+1} - 2) - \sum_{k=1}^{n-1} (2^{n+1} - 2) \\ &= & 2 n(2^n - 1) - 2 \sum_{k=1}^{n-1} (2^{n} - 1) \\ &= & 2 n(2^n - 1) - 2 [ (2^n - 2) - (n-1) ] \\ &=& 2(n2^n - 2^n + 1) \end{eqnarray} \]

Prove that \( 1 + 2 + 3 +\cdots + n = \dfrac {n(n+1)}2 \) using summation by parts.

---

We can express \( 1 + 2 + 3 +\cdots + n \) as \( \displaystyle \sum_{k=1}^n k \).

Set \(a_k = 1, b_k = k\), then \(S_k = k \), \(b_k - b_{k+1} = k - (k+1) = - 1\), \(S_0 = 0\).

\[ \require{cancel} \begin{eqnarray} \sum_{k=1}^n k &=& \displaystyle \sum _{ k=1 }^{ n }{ { a }_{k }{ b }_{k } } \\ &=& \left[ { S }_{ n }{ b }_{ n }-\cancelto0{{ S }_{ 0 }{ b }_{ 1 }} \right] +\sum _{ k=1 }^{ n-1 }{ \left[ { S }_{ k }\left( { b }_{ k }-{ b }_{ k+1 } \right) \right] } \\ &=& (n)(n) + \sum_{k=1}^{n-1} k (-1) \\ &=& n^2- \sum_{k=1}^{n-1} k \\ &=& n^2- \left[ \left( \sum_{k=1}^n k \right) - n \right ] \\ 2\sum_{k=1}^n k &=& n^2 + n = n(n+1) \\ \sum_{k=1}^n k &=& \dfrac{n(n+1)}2 \end{eqnarray} \]

Prove that \(\displaystyle \sum_{k=1}^n H_k = (n+1) (H_{n+1} - 1) \), where \( H_n\) denotes the \(n^\text{th} \) harmonic number, \( H_n = 1 + \dfrac12 + \dfrac13 + \cdots + \dfrac1n\).

---

Set \(a_k = 1, b_k = H_k \), then \(S_k = k\), \(b_k - b_{k+1} = -\dfrac1{k+1} \).

The sum becomes

\[ \require{cancel}\begin{eqnarray} \sum_{k=1}^n H_k &= & S_n b_n - \cancelto0{ S_{0} b_1} + \sum_{k=1}^{n-1} ( S_k (b_k - b_{k+1})) \\ &= & n H_n - {\sum_{k=1}^{n-1} \dfrac k{k+1} } \\ &= & n H_n - \left[ \sum_{k=1}^{n-1} \dfrac {k+1 - 1}{k+1} \right ] \\ &= & n H_n - \left[ \sum_{k=1}^{n-1} \left( 1 - \dfrac1{k+1} \right)\right ] \\ &= & n H_n - \left[ (n-1) - \left( \dfrac12 + \dfrac13 + \dfrac14 + \cdots + \dfrac1{n} \right) \right ] \\ &= & n H_n - (n-1) + (H_n - 1) \\ &= & (n+1) (H_{n+1} - 1) \end{eqnarray} \]