Unit 3-Lecture1: Sum & Product

1 Sums

1.1 Integral method

Theorem: let f:R+→R+$f: R^+ /to R^+$ be weakly increasing function. Define S::=∑i=1nf(i) $$S ::= /sum_{i=1}^nf(i)$$ and I::=∫n1f(x)dx $$I ::= /int_1^nf(x)dx$$ then I+f(1)≤S≤I+f(n) $$I+f(1)/le S /le I+f(n)$$

1.2 Asymptotically equal

Definition: For functions f,g:R→R$f, g : R /to R$, we say f$f$ is asymtotically equal to g$g$ iff limx→∞f(x)g(x)=1 $$/lim_{x/to /infty}/frac{f(x)}{g(x)} = 1$$

2 PRoducts

Stirling’s Formula

Reference

[1] Lehman E, Leighton F H, Meyer A R. Mathematics for Computer Science[J]. 2015.