Prove summation by parts:
$$ \sum_{n=1}^N a_n b_n = a_N B_N - \sum_{n=1}^{N-1}(a_{n+1} - a_n) B_n $$ where $B_N$ means $\sum_{n=1}^N b_n$ and $B_0 = 0$.
The proof is via induction. The base case is trivial. Then, given the identity up to $N$, we write:
$$ a_{N+1}B_{N+1} - a_{N+1} B_N = a_{N+1} b_{N+1} \\ a_{N+1}B_{N+1} - a_N B_N - a_{N+1} B_N + a_N B_N = a_{N+1} b_{N+1} \\ a_{N+1}B_{N+1} - a_N B_N - (a_{N+1} - a_N)B_N = a_{N+1} b_{N+1} \\ a_{N+1}B_{N+1} - a_N B_N - [\sum_{n=1}^{N}(a_{n+1} - a_n) B_n - \sum_{n=1}^{N-1}(a_{n+1}-a_n)B_n] = a_{N+1} b_{N+1} \\ a_{N+1}B_{N+1} - \sum_{n=1}^{N}(a_{n+1} - a_n) B_n - [a_N B_N - \sum_{n=1}^{N-1}(a_{n+1}-a_n)B_n] = a_{N+1} b_{N+1} \\ a_{N+1}B_{N+1} - \sum_{n=1}^{N}(a_{n+1} - a_n) B_n = a_{N+1} b_{N+1} + \sum_{n=1}^N a_n b_n\\ \\ $$
QED.
Questions:
A. Is my proof correct? Well-written? Please share your feedback and recommendations, both for the approach and the writing.
B. How would you set out to prove this? My sequence was:
- Think how I would express $\sum a_nb_n$ in terms of $B_N$
- Realize that $a_3B_3 = a_3(b_1 + b_2 + b3) + a correction factor$, and that correction factor would telescope
- This turned the identity to be proven into something that actually made sense intuitively
- I realized the proof would then follow from induction
- The induction was difficult, due to the complexity of the terms and subscripts; I eventually painstakingly worked it backwards (from the desired difference towards the original identity), and then rewrote it forwards. My writeup is a bit verbose, but I found that without that, I myself couldn't keep all the terms and subscripts straight
C. Finally: If you were, as a student, to read this proof, how would you reverse engineer the process used to produce it, so that you could learn to do so on your own? Too often, I read proofs, have no issue with them, but seem like they were pulled out of a hat.