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

Question

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 ?

Answer 1

Let us rewrite the inequality as \begin{equation} S_n \leqslant \frac{c}{a} \leqslant S_{n+1} \, , \end{equation} 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 \begin{equation} \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}}) \, . \end{equation} By summation over $i$, one obtains for all $n$ \begin{equation} S_n < \underbrace{\int_{0}^{(n+1)/b} f(x) \, dx}_{I_{n+1}} < S_{n+1} - S_0 < S_{n+1} \, , \end{equation} 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, \begin{equation} n = \left\lfloor b \left( 1 - \exp\left(-\frac{c}{a}\right)\right) \right\rfloor , \end{equation} where $\lfloor\cdot \rfloor$ denotes the floor function. Otherwise, $I_{n+1} \leqslant c/a \leqslant S_{n+1}$, and \begin{equation} n = \left\lfloor b \left( 1 - \exp\left(-\frac{c}{a}\right)\right) \right\rfloor - 1 \, . \end{equation}