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.
What sums should everyone know?
2
$\begingroup$
soft-question
-
1[This](http://www.tug.org/texshowcase/cheat.pdf) possibly contains all you need. – 2012-09-25
2 Answers
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.