# Comparison of the order of two functions

This is along the lines of Problem 9.8. in 'Concrete Mathematics' by Graham, Knuth and Patashnik.

Does any of the relation $\prec$, $\succ$ or $\sim$ exist between functions $f(n) =\displaystyle \sum_{k=0}^{n}k^{\lfloor \cos (k) \rfloor}$ and $g(n) =n^{\frac{3}{2}}$?

Both definitely diverge monotone to infinity, but I can't get my head around the rest.

-
@sigma: the summation be over $n$? – user17762 May 31 '11 at 4:33
@sigma: Also, do you mean to write $f(n) = \displaystyle\sum_{k=0}^n k^{\lfloor \cos k \rfloor}$? – JavaMan May 31 '11 at 4:38
You may not be imitating the problem closely enough. I am not able to guess what is intended, perhaps $\sum_{k=0}^n k^{\lfloor\cos k\rfloor}$. – André Nicolas May 31 '11 at 4:38
@sigma.z.1980: $f$ as you have written it does not depend on $n$, it is "constant" sort of, actually infinite, or more properly does not exist. – André Nicolas May 31 '11 at 4:49
It is a standard fact that $\pi$ is irrational. (I am assuming that as usual by $\cos(x)$ you mean the cosine function, where $x$ is measured in radians.) – André Nicolas May 31 '11 at 5:10

Since $\cos k \in (-1,1)$ for any positive integer $k$, $\left\lfloor {\cos k} \right\rfloor \in \{ 0, - 1\}$. Hence, $$f(n) = \sum\limits_{k = 0}^n {k^{\left\lfloor {\cos k} \right\rfloor } } \le \sum\limits_{k = 1}^n {k^0 } = n.$$
@Shai: What if $\lfloor \cos k \rfloor$ is replaced by $\lceil \cos k \rceil$? – JavaMan May 31 '11 at 5:15
It is not hard to see that $\cos k$ is often positive, since we are advancing by about $60$ degrees each time. That forces the altered version of $f$ to lie between $an^2$ and $bn^2$ for positive constants $a$ and $b$. – André Nicolas May 31 '11 at 5:47
@Shai: Thank you. @user6312: $1$ radian is about $57^{\circ}$, but I would think that $\{\cos k\}_{k \in \Bbb{N}}$ would be pretty equidistributed. I may think about this more, and possibly start a new thread for this new question. – JavaMan May 31 '11 at 5:56