Consider the two sequences { a n } n = 1 ∞ { \left\{ { a }_{ n } \right\} }_{ n=1 }^{ \infty } { a n } n = 1 ∞ { b n } n = 1 ∞ { \left\{ { b }_{ n } \right\} }_{ n=1 }^{ \infty } { b n } n = 1 ∞ S N = ∑ n = 1 N a n \displaystyle { S }_{ N }=\sum _{ n=1 }^{ N }{ { a }_{ n } } S N = n = 1 ∑ N a n n th n^\text{th} n th 0 ≤ m ≤ n 0 \le m \le n 0 ≤ m ≤ n
∑ k = m n a k b k = [ S n b n − S m − 1 b m ] + ∑ k = m n − 1 [ S k ( b k − b k + 1 ) ] \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] } k = m ∑ n a k b k = [ S n b n − S m − 1 b m ] + k = m ∑ n − 1 [ S k ( b k − b k + 1 ) ]
The summation can be rearranged to
∑ k = m n a k b k = ∑ k = m n [ ( S k − S k − 1 ) b k ] = ∑ k = m n S k b k − ∑ k = m n S k − 1 b k = ∑ k = m n S k b k − ∑ k = m − 1 n − 1 S k b k + 1 = ( S m b m + S m + 1 b m + 1 + S m + 2 b m + 2 + ⋯ + S n b n ) − ( S m − 1 b m + S m b m + 1 + S m + 1 b m + 2 + ⋯ + S n − 1 b n ) = [ 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 ) + ⋯ + S n − 1 ( b n − 1 − b n ) = [ S n b n − S m − 1 b m ] + ∑ k = m n − 1 [ S k ( b k − b k + 1 ) ] \begin{aligned}
\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{aligned} k = m ∑ n a k b k = = = = = = k = m ∑ n [ ( S k − S k − 1 ) b k ] k = m ∑ n S k b k − k = m ∑ n S k − 1 b k k = m ∑ n S k b k − k = m − 1 ∑ n − 1 S k b k + 1 ( S m b m + S m + 1 b m + 1 + S m + 2 b m + 2 + ⋯ + S n b n ) − ( S m − 1 b m + S m b m + 1 + S m + 1 b m + 2 + ⋯ + S n − 1 b n ) [ 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 ) + ⋯ + S n − 1 ( b n − 1 − b n ) [ S n b n − S m − 1 b m ] + k = m ∑ n − 1 [ S k ( b k − b k + 1 ) ]
Find ∑ k = 1 n k 2 k \displaystyle \sum _{ k=1 }^{ n }{ k{ 2 }^{ k } } 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 a_k = 2^k a k = 2 k b k = k b_k = k b k = k S n = ∑ k = 1 n a k S_n = \sum_{k=1}^n a_k S n = ∑ k = 1 n a k geometric progression sum , S n = 2 n + 1 − 2 S_n = 2^{n+1} - 2 S n = 2 n + 1 − 2 b k − b k + 1 = k − ( k + 1 ) = − 1 b_k - b_{k+1} = k - (k+1) = -1 b k − b k + 1 = k − ( k + 1 ) = − 1 S 0 = ∑ k = 1 0 a k = 0 S_0 = \sum_{k=1}^0 a_k= 0 S 0 = ∑ k = 1 0 a k = 0
Plugging everything into the formula gives
∑ k = 1 n k 2 k = ∑ k = 1 n a k b k = S n b n − S 0 b 1 0 + ∑ k = 1 n − 1 [ S k ( b k − b k + 1 ) − 1 ] = n ( 2 n + 1 − 2 ) − ∑ k = 1 n − 1 S k = n ( 2 n + 1 − 2 ) − ∑ k = 1 n − 1 ( 2 n + 1 − 2 ) = 2 n ( 2 n − 1 ) − 2 ∑ k = 1 n − 1 ( 2 n − 1 ) = 2 n ( 2 n − 1 ) − 2 [ ( 2 n − 2 ) − ( n − 1 ) ] = 2 ( n 2 n − 2 n + 1 ) \begin{aligned}
\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{aligned} k = 1 ∑ n k 2 k = = = = = = = k = 1 ∑ n a k b k S n b n − S 0 b 1 0 + k = 1 ∑ n − 1 [ S k ( b k − b k + 1 ) − 1 ] n ( 2 n + 1 − 2 ) − k = 1 ∑ n − 1 S k n ( 2 n + 1 − 2 ) − k = 1 ∑ n − 1 ( 2 n + 1 − 2 ) 2 n ( 2 n − 1 ) − 2 k = 1 ∑ n − 1 ( 2 n − 1 ) 2 n ( 2 n − 1 ) − 2 [ ( 2 n − 2 ) − ( n − 1 ) ] 2 ( n 2 n − 2 n + 1 )
Prove that 1 + 2 + 3 + ⋯ + n = n ( n + 1 ) 2 1 + 2 + 3 +\cdots + n = \dfrac {n(n+1)}2 1 + 2 + 3 + ⋯ + n = 2 n ( n + 1 )
We can express 1 + 2 + 3 + ⋯ + n 1 + 2 + 3 +\cdots + n 1 + 2 + 3 + ⋯ + n ∑ k = 1 n k \displaystyle \sum_{k=1}^n k k = 1 ∑ n k
Set a k = 1 , b k = k a_k = 1, b_k = k a k = 1 , b k = k S k = k S_k = k S k = k b k − b k + 1 = k − ( k + 1 ) = − 1 b_k - b_{k+1} = k - (k+1) = - 1 b k − b k + 1 = k − ( k + 1 ) = − 1 S 0 = 0 S_0 = 0 S 0 = 0
∑ k = 1 n k = ∑ k = 1 n a k b k = [ S n b n − S 0 b 1 0 ] + ∑ k = 1 n − 1 [ S k ( b k − b k + 1 ) ] = ( n ) ( n ) + ∑ k = 1 n − 1 k ( − 1 ) = n 2 − ∑ k = 1 n − 1 k = n 2 − [ ( ∑ k = 1 n k ) − n ] 2 ∑ k = 1 n k = n 2 + n = n ( n + 1 ) ∑ k = 1 n k = n ( n + 1 ) 2
\begin{aligned} \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{aligned} k = 1 ∑ n k 2 k = 1 ∑ n k k = 1 ∑ n k = = = = = = = k = 1 ∑ n a k b k [ S n b n − S 0 b 1 0 ] + k = 1 ∑ n − 1 [ S k ( b k − b k + 1 ) ] ( n ) ( n ) + k = 1 ∑ n − 1 k ( − 1 ) n 2 − k = 1 ∑ n − 1 k n 2 − [ ( k = 1 ∑ n k ) − n ] n 2 + n = n ( n + 1 ) 2 n ( n + 1 )
Prove that ∑ k = 1 n H k = ( n + 1 ) ( H n + 1 − 1 ) \displaystyle \sum_{k=1}^n H_k = (n+1) (H_{n+1} - 1) k = 1 ∑ n H k = ( n + 1 ) ( H n + 1 − 1 ) H n H_n H n n th n^\text{th} n th harmonic number , H n = 1 + 1 2 + 1 3 + ⋯ + 1 n H_n = 1 + \dfrac12 + \dfrac13 + \cdots + \dfrac1n H n = 1 + 2 1 + 3 1 + ⋯ + n 1
Set a k = 1 , b k = H k a_k = 1, b_k = H_k a k = 1 , b k = H k S k = k S_k = k S k = k b k − b k + 1 = − 1 k + 1 b_k - b_{k+1} = -\dfrac1{k+1} b k − b k + 1 = − k + 1 1
The sum becomes
∑ k = 1 n H k = S n b n − S 0 b 1 0 + ∑ k = 1 n − 1 ( S k ( b k − b k + 1 ) ) = n H n − ∑ k = 1 n − 1 k k + 1 = n H n − [ ∑ k = 1 n − 1 k + 1 − 1 k + 1 ] = n H n − [ ∑ k = 1 n − 1 ( 1 − 1 k + 1 ) ] = n H n − [ ( n − 1 ) − ( 1 2 + 1 3 + 1 4 + ⋯ + 1 n ) ] = n H n − ( n − 1 ) + ( H n − 1 ) = ( n + 1 ) ( H n + 1 − 1 ) \begin{aligned}
\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{aligned}
k = 1 ∑ n H k = = = = = = = S n b n − S 0 b 1 0 + k = 1 ∑ n − 1 ( S k ( b k − b k + 1 ) ) n H n − k = 1 ∑ n − 1 k + 1 k n H n − [ k = 1 ∑ n − 1 k + 1 k + 1 − 1 ] n H n − [ k = 1 ∑ n − 1 ( 1 − k + 1 1 ) ] n H n − [ ( n − 1 ) − ( 2 1 + 3 1 + 4 1 + ⋯ + n 1 ) ] n H n − ( n − 1 ) + ( H n − 1 ) ( n + 1 ) ( H n + 1 − 1 )