# rudin's summation by parts

3.41 Theorem Given two sequences $\left\{a_n\right\}$,$\left\{b_n\right\}$,put

\begin{align*}A_n=\sum _{k=0}^n a_k~~~(1)\end{align*}

if $n\geq 0$; put $A_{-1}=0$. Then, if $0\leq p\leq q$, we have

\begin{align*}\sum _{n=p}^q a_nb_n=\sum _{n=p}^{q-1} A_n\left(b_n-b_{n+1}\right)+\color{blue}{A_qb_q}\color{red}{-}\color{blue}{A_{p-1}b_p}.~~~(2)\end{align*}

wiki's summation by parts

## My derivation:

blue color highlight the changed item.

## Questions

### question1:

The blue part of (2) is a little hard to memorize before I've done the calculation.

What's the relation between (2) and the Integration by parts which I think is easier to memorize (without those indexes).

$\int f dg=f g-\int f dg$

or

$\int _a^bF(x)g(x)dx=F(b)G(b)-F(a)G(a)-\int _a^bf(x)G(x)dx$

### question2:

What's the guidelines to derive the (2)?

As you see the wiki's edition, there are also several versions.

Although I get (2), I did it by cheating, i.e. I'm doing proof, and I checked (2) in my process of derivation.

Of course, the proof in text, is much easier:

\begin{align*}\sum _{n=p}^q a_nb_n=\sum _{n=p}^q \left(A_n-A_{n-1}\right)b_n=\sum _{n=p}^q A_nb_n-\sum _{n=p-1}^{q-1} A_nb_{n+1}~~~(4)\end{align*}

,and the last expression on the right is clearly equal to the right side of (2)

### question3

$A_n$is summation from $0$ to $n$, how does it look reasonable when $p=5$?

-
Any suggestions about latex and writings are also welcome, I'm novice in SE. – HyperGroups Jul 1 '13 at 16:57
Yes, the calculation is correct. – Brian M. Scott Jul 1 '13 at 21:38
@BrianM.Scott hi, thanks for verification, I've added my further questions. – HyperGroups Jul 2 '13 at 5:05
MathJax so slow and stuck when editing in SE. Should I use image for large DisplayFormula.? – HyperGroups Jul 2 '13 at 5:33

Define $$A_n=\sum_{k=1}^na_k\quad\text{and}\quad F(x)=\int_a^xf(t)\,\mathrm{d}t$$

Question 1:

Consider summation by parts $$\sum_{k=m}^na_kb_k =A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k)$$ vs integration by parts $$\int_a^bf(x)g(x)\,\mathrm{d}x=F(b)g(b)-F(a)g(a)-\int_a^bF(x)g'(x)\,\mathrm{d}x$$ The parallel seems pretty clear.

Question 2:

I'm not sure what you mean by guidelines to derive summation by parts. Basically, summation by parts is just a change of the index of summation. \begin{align} \sum_{k=m}^na_kb_k &=\sum_{k=m}^n(A_k-A_{k-1})b_k\\ &=\sum_{k=m}^nA_kb_k-\sum_{k=m}^nA_{k-1}b_k\\ &=\sum_{k=m}^nA_kb_k-\sum_{k=m-1}^{n-1}A_kb_{k+1}\\ &=A_nb_n+\sum_{k=m}^{n-1}A_kb_k-A_{m-1}b_m-\sum_{k=m}^{n-1}A_kb_{k+1}\\ &=A_nb_n-A_{m-1}b_m+\sum_{k=m}^{n-1}A_k(b_k-b_{k+1}) \end{align}

Question 3:

$$\sum_{k=5}^na_kb_k =A_nb_n-A_4b_5-\sum_{k=5}^{n-1}A_k(b_{k+1}-b_k)$$ It looks reasonable to me. If you're worried about where the summation starts, that only alters $A_n$ by a constant. Consider how much a constant added to $A_n$ changes the value of the summation by parts formula: \begin{align} &(A_n+C)b_n-(A_{m-1}+C)b_m-\sum_{k=m}^{n-1}(A_k+C)(b_{k+1}-b_k)\\ &=A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k)\\ &+C\left(b_n-b_m-\sum_{k=m}^{n-1}(b_{k+1}-b_k)\right)\\ &=A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k)\\ &+C(b_n-b_m-(b_n-b_m))\\ &=A_nb_n-A_{m-1}b_m-\sum_{k=m}^{n-1}A_k(b_{k+1}-b_k) \end{align} $C$ has no effect on the final value of the formula.

-
Ah, your form is much better parallel to integration by parts. Why your $A_n=\sum _{k=1}^n a_k$, not $A_n=\sum _{k=0}^n a_k$? – HyperGroups Jul 2 '13 at 8:33
@HyperGroups: as I showed in my answer to Question 3, it doesn't matter where you start the summation for $A_n$. – robjohn Jul 2 '13 at 8:36
got it, thanks. $\sum _{k=m}^n a_kb_k=A_nb_n-A_{\color{red}{m}}b_m-\sum _{k=m}^{\color{red}{n}} A_k\left(b_{k+1}-b_k\right)$if without calculation, maybe I'll write some indexes wrongly when recall this formula like this, do you think it's more perfect? of course its wrong.... – HyperGroups Jul 2 '13 at 9:01
The guidelines mean some rules when changing of index of summation. Sometimes I feel it hard to choose which change is the fastest, most efficient, and needed, and when to stop. For example, this is one rule,$\sum _{k=m}^n A_{k-1}b_k$, here I wanna make $A_{k-1}$ becomes $A_k$, so I change to $\sum _{k=m-1}^{n-1} A_kb_{k+1}$. – HyperGroups Jul 2 '13 at 9:11
Thanks @robjohn for the nice and simple derivations :-) – User001 Nov 24 '15 at 0:15