2
$\begingroup$

Well, everyone is an overstatement. Qualifying it: I'm interested in algorithms (complexity) and probabilistic processes/models and I often see sums converge to a certain value in the books I'm reading (algorithm iterations and finite and infinite series of probabilities etc.). I'm looking for a reference (website for example) that contains common sums and their convergence values (infinite or finite) that are often times encountered in these subjects.

  • 0
    Gradshteyn and Ryzhik's Table of Integrals, Series, and Products may be useful2012-09-25
  • 1
    [This](http://www.tug.org/texshowcase/cheat.pdf) possibly contains all you need.2012-09-25

2 Answers 2

1

Geometric Series and its derivatives are very common in complexity problems as well as probabilistic models.

$$a+ar+ar^2+\cdots+ar^{n-1}=\frac{a(r^n-1)}{r-1}$$

For $|r|<1,$ infinite geometric series converges

$$a+ar+ar^2+\cdots =\frac{a}{1-r}$$

Binomial expansion is also common

$$(a+b)^n={n\choose 0}a^{n}b^{0}+{n\choose 1}a^{n-1}b^{1}+\cdots+{n\choose k}a^{n-k}b^{k}+\cdots +{n\choose n}a^{0}b^{n} $$

2

Perhaps we can interest you in the book Concrete Mathematics. For an enthusiastic student who has not necessarily mastered similar material before, it teaches quite a variety of summation techniques with algorithm analysis in mind.