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$
  • $\begingroup$ Perhaps use the inequalities $k-1<\lfloor k\rfloor\leq k$ for a lower and upper bound. $\endgroup$ – kingW3 Sep 22 '17 at 2:46
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$
  • $\begingroup$ Thanks for this answer and the useful hints! Could you please discuss the last example in the question? $\endgroup$ – Linus Rastegar Sep 22 '17 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$ – Ross Millikan Sep 22 '17 at 14:20

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.