Summation By Parts
In mathematics, summation by parts transforms the summation of sequences into the summations of other sequences, often simplifying the calculation or estimation of certain types of sums. Summation by parts is analogous to integration by parts.
Introduction
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=m}^{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} \]