What sums should everyone know?

Question

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.

Answer 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} $$

Answer 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.