Consider the two sequences and . Let be the partial sum. Then for we have:
The summation can be rearranged to
This sum can be solved using arithmetic-geometric progression, but solving it via summation by parts is so much more fun!
First, we let and . Then, the partial sum can be found using the geometric progression sum, . And . Lastly, by definition, .
Plugging everything into the formula gives
Prove that using summation by parts.
We can express as .
Set , then , , .
Prove that , where denotes the harmonic number, .
Set , then , .
The sum becomes