# Inequality involving sum with parameter in denominator (leading to harmonic number problem)

Given integers $a$, $b$ and $c$, I am trying to find $n \leq b-1$ such that this inequality holds :

$$\sum\limits_{i=0}^{n} \frac{a}{b - i} \leq c \leq \sum\limits_{i=0}^{n+1} \frac{a}{b - i}$$

That is to say : the largest $n$ up to which the sum is the closest to $c$ .

Since : $$\sum\limits_{i=0}^{n} \frac{a}{b - i} = a \cdot (\sum\limits_{i=0}^{b} \frac{1}{i} - \sum\limits_{i=0}^{b-n-1} \frac{1}{i})$$

And $\sum\limits_{i=0}^{k} \frac{1}{i} = H_k$ where $H_k$ is the $k$-th harmonic number,

We can rewrite the inequality into :

$$a(H_{b} - H_{b-n-1}) \leq c \leq a(H_{b} - H_{b-n-2})$$

How to find a tight lower and upper bound for $n$, such that this inequality holds ?

Let us rewrite the inequality as $$S_n \leqslant \frac{c}{a} \leqslant S_{n+1} \, ,$$ where $S_n = \frac{1}{b} \sum_{i=0}^n f(\frac{i}{b})$ and $f$ is defined by $x \mapsto \frac{1}{1-x}$ for $x$ in $[0,1[$. Thus, one can view $S_n$ as the rectangle method of numerical integration applied to $f$. Since $f$ is strictly increasing, one has $$\frac{1}{b} f({\textstyle\frac{i}{b}}) < \int_{i/b}^{(i+1)/b} f(x) \, dx < \frac{1}{b} f({\textstyle\frac{i+1}{b}}) \, .$$ By summation over $i$, one obtains for all $n$ $$S_n < \underbrace{\int_{0}^{(n+1)/b} f(x) \, dx}_{I_{n+1}} < S_{n+1} - S_0 < S_{n+1} \, ,$$ where the integral is given by $I_{n+1} = -\ln(1-{\textstyle\frac{n+1}{b}})$. Let us examine two cases:
• if $c/a$ is larger than $S_{b-1}$, then no such $n$ can be found. Taking $n=b-1$ insures $S_n \leqslant c/a$ only.
• else, we can find $n$ such that the first inequality is satisfied. If $S_n \leqslant c/a < I_{n+1}$, then $I_n < c/a < I_{n+1}$. Therefore, $$n = \left\lfloor b \left( 1 - \exp\left(-\frac{c}{a}\right)\right) \right\rfloor ,$$ where $\lfloor\cdot \rfloor$ denotes the floor function. Otherwise, $I_{n+1} \leqslant c/a \leqslant S_{n+1}$, and $$n = \left\lfloor b \left( 1 - \exp\left(-\frac{c}{a}\right)\right) \right\rfloor - 1 \, .$$
• Thank you so much :-) I like this method. I found a similar upper bound by solving the inequality with harmonic numbers : $n < b(1 - \frac{1}{\sqrt{e} \cdot e^\frac{c}{a}}) - 1$. But your upper bound is tighter and your method is useful since it is more general and can be used to solve other inequalities with similar sums. I'm going to work on it... thanks again :-) – Luz Mar 1 '17 at 19:12