1
$\begingroup$

When solving optimization problems, analyzing and simplifying sums, solving related rates problems, etc., there is always a procedure and a best practice to follow to arrive at a good answer. I've come across many sums with plenty of floors--my own interests bring me to these very sums! In most cases where a sum with the floor function is considered, some lower and upper bounds or error term is given. Since I've never taken a course where these sorts of error terms are discussed specifically in sums involving floor functions, what steps can I take to arrive at a tight error bound for a floor function?

E.G:

  1. What would be the process in finding the error for $\sum_{k=0} ^ r \lfloor \frac{f(k)}{k} \rfloor$ for $r$ a fixed constant and $f(x)$ a function?

  2. What would be the process in finding the error for $\sum_{k=0} ^ \infty \lfloor \frac{f(k)}{k} \rfloor$? For $\sum_{k=0} ^ \infty \lfloor \frac{f(k)}{g(k)} \rfloor$? For $\sum_{k=0} ^ \infty \lfloor \frac{f(k)}{g(k)} \rfloor h(k)$? For $\sum_{k=0} ^ \infty \lfloor \frac{f(k)}{k} \rfloor (-1)^k$?

Any references to an appopriate resource would also be appreciated! Also, please discuss the process you would use to find an error term for the following example in your answer: $\sum_{k=0} ^ \infty (-1)^k \lfloor \frac{k^2}{\ln k} \rfloor$

$\endgroup$
1
  • $\begingroup$ Perhaps use the inequalities $k-1<\lfloor k\rfloor\leq k$ for a lower and upper bound. $\endgroup$
    – kingW3
    Sep 22, 2017 at 2:46

1 Answer 1

1
$\begingroup$

My process is to think about it, as it depends on $f(k)$. One extreme is $0 \le f(k) \lt k$ when $0 \le \frac {f(k)}k \lt 1$ and the sum is zero. If $\frac {f(k)}k$ is slowly varying you can find big regions where the floor is constant and spend your time looking for where it changes. If $\frac {f(k)}k$ bounces around a lot you can assume the floor costs you about $\frac 12$ each time, deduct that from the sum, and delete the floor signs. That may help. You might be able to convert to an integral once the floors are gone.

$\endgroup$
2
  • $\begingroup$ Thanks for this answer and the useful hints! Could you please discuss the last example in the question? $\endgroup$ Sep 22, 2017 at 12:15
  • $\begingroup$ The last one is hard because it could be that $\frac {f(k)}k$ is just above an integer for odd indices and just below for even or something like that. You have to look carefully at $f(k)$. $\endgroup$ Sep 22, 2017 at 14:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .