Approximating summations via integrals

45 Views Asked by At

I am currently taking an algorithms course, which explains how summations can be bounded by integrals.

The rule for this is $$\int_{m}^{n+1} f(x) dx \leq \sum_{k=m}^{n}f(k) \leq \int_{m-1}^{n} f(x) dx.$$

It then runs through an example, where it bounds the summation from below $$ \sum_{k=1}^{n} \frac{1}{k} \geq \int_{1}^{n+1} \frac{dx}{x} = ln(n+1) $$ and from above $$ \sum_{k=2}^{n} \frac{1}{k} \leq \int_{1}^{n} \frac{dx}{x} = ln(n) $$ after which a $1$ is added for starting the summation from $k=2$.

Here is where my confusion lies however; what was the need to start the summation from $k=2$ and why couldn't we just start it from $1$ like when bounding from below.

1

There are 1 best solutions below

0
On BEST ANSWER

$\int_0^{1} \frac 1 x dx$ does not exist so you consider $\int_k^{k+1} \frac 1 x dx$ for $k=1,2,3..$ and and add them to derive those inequalities.

Note that $\int_k^{k+1} \frac 1 x dx >\frac 1 {k+1}$ and $\int_k^{k+1} \frac 1 x dx <\frac 1 k$ for each $k \in \mathbb N$.