 # Given integers a, b and c, I am trying to find n<=b−1 such that this inequality holds : sum_(i=0)^(n)(a)/(b - i) <= c <= sum_(i=0)^(n+1)(a)/(b-i) That is to say : the largest n up to which the sum is the closest to c . Since : sum_(i=0)^(n)(a)/(b-i)=a*(sum_(i=0)^(b)(1)/(i)-sum_(i=0)^(b-n-1)(1)/(i)) And sum_(i=0)^k 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))<=c<=a(H_b−H_(b−n−2)) How to find a tight lower and upper bound for n, such that this inequality holds ? Aleah Booth 2022-07-17 Answered
Inequality involving sum with parameter in denominator (leading to harmonic number problem)
Given integers $a$, $b$ and $c$, I am trying to find $n\le b-1$ such that this inequality holds :
$\sum _{i=0}^{n}\frac{a}{b-i}\le c\le \sum _{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 _{i=0}^{n}\frac{a}{b-i}=a\cdot \left(\sum _{i=0}^{b}\frac{1}{i}-\sum _{i=0}^{b-n-1}\frac{1}{i}\right)$
And $\sum _{i=0}^{k}\frac{1}{i}={H}_{k}$ where ${H}_{k}$ is the $k$-th harmonic number,
We can rewrite the inequality into :
$a\left({H}_{b}-{H}_{b-n-1}\right)\le c\le a\left({H}_{b}-{H}_{b-n-2}\right)$
How to find a tight lower and upper bound for $n$, such that this inequality holds ?
You can still ask an expert for help

• Live experts 24/7
• Questions are typically answered in as fast as 30 minutes
• Personalized clear answers

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it agyalapi60
Let us rewrite the inequality as
${S}_{n}⩽\frac{c}{a}⩽{S}_{n+1}\phantom{\rule{thinmathspace}{0ex}},$
where ${S}_{n}=\frac{1}{b}\sum _{i=0}^{n}f\left(\frac{i}{b}\right)$ and $f$ is defined by $x↦\frac{1}{1-x}$ for $x$ in $\left[0,1\left[$. 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\left(\frac{i}{b}\right)<{\int }_{i/b}^{\left(i+1\right)/b}f\left(x\right)\phantom{\rule{thinmathspace}{0ex}}dx<\frac{1}{b}f\left(\frac{i+1}{b}\right)\phantom{\rule{thinmathspace}{0ex}}.$
By summation over $i$, one obtains for all $n$
${S}_{n}<\underset{{I}_{n+1}}{\underset{⏟}{{\int }_{0}^{\left(n+1\right)/b}f\left(x\right)\phantom{\rule{thinmathspace}{0ex}}dx}}<{S}_{n+1}-{S}_{0}<{S}_{n+1}\phantom{\rule{thinmathspace}{0ex}},$
where the integral is given by ${I}_{n+1}=-\mathrm{ln}\left(1-\frac{n+1}{b}\right)$. 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}⩽c/a$ only.
else, we can find $n$ such that the first inequality is satisfied. If ${S}_{n}⩽c/a<{I}_{n+1}$, then ${I}_{n}. Therefore,
$n=⌊b\left(1-\mathrm{exp}\left(-\frac{c}{a}\right)\right)⌋,$
where $⌊\cdot ⌋$ denotes the floor function. Otherwise, ${I}_{n+1}⩽c/a⩽{S}_{n+1}$, and
$n=⌊b\left(1-\mathrm{exp}\left(-\frac{c}{a}\right)\right)⌋-1\phantom{\rule{thinmathspace}{0ex}}.$

We have step-by-step solutions for your answer!