Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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. enter image description here

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$?

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.