Inequality involving sum with parameter in denominator (leading to harmonic number problem)Given integers a, b and c, I am trying to find n ≤ b − 1 such that this inequality holds : ∑ i = 0 n a b − i ≤ c ≤ ∑ i = 0 n + 1 a b − i That is to say : the largest n up to which the sum is the closest to cSince : ∑ i = 0 n a b − i = a ⋅ ( ∑ i = 0 b 1 i − ∑ i = 0 b − n − 1 1 i )And ∑ 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 ?

Question

Inequality involving sum with parameter in denominator (leading to harmonic number problem)Given integers   a,   b and   c, I am trying to find   n  ≤  b  −  1 such that this inequality holds :      ∑          i      =      0              n            a          b      −      i        ≤  c  ≤      ∑          i      =      0              n      +      1            a          b      −      i      That is to say : the largest   n up to which the sum is the closest to   cSince :      ∑          i      =      0              n            a          b      −      i        =  a  ⋅  (      ∑          i      =      0              b            1    i    −      ∑          i      =      0              b      −      n      −      1            1    i    )And       ∑          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 ?

agyalapi60 · Accepted Answer

Let us rewrite the inequality as      S    n    ⩽      c    a    ⩽      S          n      +      1          ,where       S    n    =      1    b        ∑          i      =      0        n    f  (      i    b    ) and   f is defined by   x  ↦      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      1    b    f  (                    i        b              )  &amp;lt;      ∫          i              /            b              (      i      +      1      )              /            b        f  (  x  )    d  x  &amp;lt;      1    b    f  (                              i          +          1                b              )    .By summation over   i, one obtains for all   n      S    n    &amp;lt;                                          ∫                          0                                      (              n              +              1              )                              /                            b                                f          (          x          )                    d          x                ⏟                            I                  n          +          1                      &amp;lt;      S          n      +      1        −      S    0    &amp;lt;      S          n      +      1          ,where the integral is given by       I          n      +      1        =  −  ln  ⁡  (  1  −                              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    ⩽  c      /    a only.else, we can find   n such that the first inequality is satisfied. If       S    n    ⩽  c      /    a  &amp;lt;      I          n      +      1      , then       I    n    &amp;lt;  c      /    a  &amp;lt;      I          n      +      1      . Therefore,  n  =      ⌊    b          (      1      −      exp      ⁡              (        −                  c          a                )            )        ⌋    ,where   ⌊  ⋅  ⌋ denotes the floor function. Otherwise,       I          n      +      1        ⩽  c      /    a  ⩽      S          n      +      1      , and  n  =      ⌊    b          (      1      −      exp      ⁡              (        −                  c          a                )            )        ⌋    −  1    .

Answered question

Answer & Explanation

New Questions in Pre-Algebra