Summation by parts

\[\displaystyle {\sum^{n}_{i=1}}(a_i b_i)=\sum^{n-1}_{i=1}\left (\sum^{i}_{j=1}\left ( (b_{j}\right ) (a_{i}-a_{i+1})) \right ) + \sum^{n}_{i=1}\left (b_{i} a_{n} \right )\]

The proof of summation by parts

The algebraic proof

\[\begin{align} &\displaystyle {\sum^{n}_{i=1}}(a_i b_i) \\ =& \sum^{n}_{i=1} \left ((a_i)\left ( -\sum^{i-1}_{j=1}b_j + \sum^{i}_{j=1}b_j\right )\right) \\ =& + a_1 \color{blue}{\sum^{1}_{j=1}b_j} - a_2 \color{blue}{\sum^{1}_{j=1}b_j} \\& + a_2 \color{red}{\sum^{2}_{i=1}b_j} - a_3 \color{red}{\sum^{2}_{i=1}b_j} \\ &+\cdots \\ &+ a_{n-2} \color{green}{\sum^{n-2}_{i=1}b_{j}}- a_{n-1} \color{green}{\sum^{n-2}_{i=1}b_{j}} \\ &+ a_{n-1} \color{purple}{\sum^{n-1}_{i=1}b_{j}} - a_{n} \color{purple}{\sum^{n-1}_{i=1}b_{j}} \\ & + a_{n} \color{brown}{\sum^{n}_{i=1}b_{j}} \\ =&+ (a_1 - a_2) \color{blue}{\sum^{1}_{j=1}b_j} \\&+(a_2 - a_3) \color{red}{\sum^{2}_{j=1}b_j} \\&+ \cdots \\&+ (a_{n-2} - a_{n-3}) \color{green}{\sum^{n-2}_{j=1}b_j} \\&+ (a_{n-1} - a_{n-2}) \color{purple}{\sum^{n-1}_{j=1}b_j} \\&+ a_{n} \color{brown}{\sum^{n}_{i=1}b_{j}} \\=& + \sum^{1}_{j=1}\left (b_j(a_1 - a_2) \right ) \\&+ \sum^{2}_{j=1}\left ( b_j(a_2 - a_3) \right ) \\&+ \cdots \\&+ \sum^{n-2}_{j=1}\left ( b_j(a_{n-2} - a_{n-3})\right ) \\&+ \sum^{n-1}_{j=1}\left ( b_j(a_{n-1} - a_{n-2})\right ) \\&+ \sum^{n}_{i=1}(b_{j}a_{n}) \\=& \sum^{n-1}_{i=1}\left (\sum^{i}_{j=1}\left ( (b_{j}\right ) (a_{i}-a_{i+1})) \right ) + \sum^{n}_{i=1}\left (b_{i} a_{n} \right )\end{align}\]

The algebraic proof

Exercise

  1. Please use “summation by parts” to prove $1^2+2^2+ \cdots + (n-1)^2 +n^2 =\frac{2n^3+3n^2+n}{6}$

2.

3.

Answer key

1.

2.

\[\begin{align} \quad &1^2+2^2+ \cdots + (n-1)^2 +n^2 = \displaystyle \sum ^{n}_{i=1}i^2 \\=& \sum^{n-1}_{i=1}\left (\sum^{i}_{j=1}j(i-(i+1)) \right ) + n \sum^{n}_{i=1}i \\=&-\sum^{n-1}_{i=1}\left ( \sum^{i}_{j=1}j \right )+ n \sum^{n}_{i=1}i \\=& -\sum^{n-1}_{i=1}\left (\frac{(1+i)i}{2}\right ) + n \sum^{n}_{i=1}i \\=& -\frac{\displaystyle \sum^{n-1}_{i=1}i^2+\sum^{n-1}_{i=1}i}{2}+n \sum^{n}_{i=1}i \\=& -\frac{\displaystyle \sum^{n}_{i=1}i^2+\sum^{n-1}_{i=1}i-n^2}{2}+n \sum^{n}_{i=1}i \\\implies & \sum ^{n}_{i=1}i^2= -\frac{\displaystyle \sum^{n}_{i=1}i^2+\sum^{n-1}_{i=1}i-n^2}{2}+n \sum^{n}_{i=1}i \\ \implies & 3\sum ^{n}_{i=1}i^2= -\sum^{n-1}_{i=1}i+n^2+2n \sum^{n}_{i=1}i \\ \implies & \sum ^{n}_{i=1}i^2=\frac{-\frac{n(n-1)}{2}+n^2+(n+1)n^2}{3} \\ \implies & \sum ^{n}_{i=1}i^2=\frac{-n^2+n+2n^2+2n^3+2n^2}{6} \\ \implies & \sum ^{n}_{i=1}i^2=\frac{2n^3+3n^2+n}{6} \end{align}\]

3.