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 \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}
  • $\begingroup$ 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 :-) $\endgroup$ – Luz Mar 1 '17 at 19:12
  • $\begingroup$ You're welcome! Note: the Euler–Maclaurin formula provides a powerful connection between integrals and sums. $\endgroup$ – Harry49 Mar 3 '17 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.