How to solve recurrence relation $T(n)=T(n-1)+\lceil \log(n) \rceil$

Question

Without the ceilings, the solution is reasonable clear (given here).

Is there a way to reach a solution with the ceilings, or the difference between the two?

Answer 1

I'll do this solution, although you may not like it, and it might not work. $$f(n+1)=f(n)+c \cdot \log(n)$$ We'll define c in a little bit. Also we'll start at $n=1$ and use the power and multiplication rules. $$f(2)=\log(1^c)+\log(2^c)=c \cdot \log(1\cdot2)$$ $$f(3)=c \cdot \log(1\cdot2)+c \cdot \log(3)=c \cdot \log(1\cdot2 \cdot 3)$$ Its fairly obvious this is just a factorial... $$f(n)=c \cdot \log(n!)$$ For generality, use the gamma function... $$f(n)=c \cdot \log(\Gamma(n+1))$$ with $c=1$, this is a famous result in and of its self. Here's the part that might upset you. c is actually the operator for the ceiling function! $$f(n)=ceiling(\log(\Gamma(n+1))$$