Upper bound to floor of log

Question

What's a good upper bound to the floor of the base k log function? i.e: $$ \lfloor \log_k(x)\rfloor\leq f(x)$$ By good I mean a rational function that grows slowly. My first attempt was $f(x)=\frac{x}{k^2}+1$.

Answer 1

Extending kimchi lover's answer, you can use the Taylor series expansion as far as you want.

If $f(x) = \log_k(x)$, then $f'(x) = \frac1{x\ln k}$, $f''(x) = \frac{-1}{x^2\ln k}$, $f'''(x) = \frac{2}{x^3\ln k}$, and so on, with $f^{(n)}(x) = \frac{(-1)^{n-1}(n-1)!}{x^n\ln k}$.

Therefore

$\begin{array}\\ f(x) &=f(a)+(x-a)f'(a)+\dfrac{(x-a)^2f''(a)}{2}+\dfrac{(x-a)^3f'''(a)}{6} +...\\ &=\log_k(a)+\dfrac{(x-a)}{a\ln k}-\dfrac{(x-a)^2}{2a^2\ln k}+\dfrac{(x-a)^3}{6a^3\ln k} +...\\ &=\log_k(a)+\dfrac{(x-a)}{a\ln k}\left(1-\dfrac{x-a}{2a}+\dfrac{(x-a)^2}{6a^2} +...\right)\\ &=\log_k(a)+\dfrac{(x-a)}{a\ln k} \left(\sum_{j=0}^n\dfrac{(-1)^j(x-a)^j}{(j+1)!a^{j}}+...\right) \qquad\text{for any }n\\ \end{array} $

Note that successive sums are above and below the actual value, so you can get upper and lower bounds.

Answer 2

You can use the fact that $\log$ is concave to get $$\log_k x \le \log_k A + (x-A)/(A \ln k)$$ for any $A>0.$ This bound is possibly useful for $x$ close to $A$, but for $x$ far from $A$, it is terrible. So if there is a range of $x$ values where your bound is supposed to do you the most good, pick $A$ in it.