Show that there exist non-decreasing $f,g:\Bbb N\to \Bbb N$ such that $f\neq O(g)$ and $g\neq O(f)$. ($\Bbb N$ is the set of strictly positive integers.)
Source: Victor Shoup's "A computational introduction to number theory and algebra".
Also, I'd be interested if this also holds for increasing functions as well.
Note: I tried building the functions such that each of them has an exponential subsequence that is linear in the other.. no success. Would this be doable?
For every $n\ge 1$, let $k(n)$ be such that $2^{k(n)}\le n< 2^{k(n)+1}$. The point of this definition is that we can write $\mathbb N_+$ as an "interleaving" $$ \mathbb N_+ = \bigcup_{k\ \text{even}}[2^k,2^{k+1})\cup\bigcup_{k\ \text{odd}}[2^k,2^{k+1}). $$ Define $$ f(n) = \begin{cases} n^{k(n)+1} & \text{if $k(n)$ is even}\\ n^{k(n)} & \text{if $k(n)$ is odd}\end{cases}\quad\text{and}\quad g(n) = \begin{cases} n^{k(n)} & \text{if $k(n)$ is even}\\ n^{k(n)+1} & \text{if $k(n)$ is odd}\end{cases}. $$ Here is a table of the values of $f(n)$ and $g(n)$ that hopefully makes it clear at a glance that $f$ and $g$ are increasing, though I added a proof at the end of the post, too. \begin{array}{|c|c|c|c|c|c|c|c|c|c|}\hline k(n)& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dots\\ \hline f(n)& n^1& n^1& n^3 & n^3 & n^5 & n^5 & n^7 & n^7 & \dots\\ \hline g(n)& n^0 & n^2 & n^2 & n^4 & n^4 & n^6 & n^6 & n^8 & \dots\\ \hline \end{array} The point of this definition is that we have: $$ \frac{f(n)}{g(n)} = \begin{cases}n & \text{if $k(n)$ is even}\\n^{-1} & \text{if $k(n)$ is odd} \end{cases}. $$ This shows that $f \ne O(g)$ and $g \ne O(f)$.
Proof that $f$ and $g$ are increasing. Clearly $f$ and $g$ are increasing for $n$ in any of the intervals of the form $[2^b,2^{b+1})$, so we only need to check $f(2^{b}-1)< f(2^{b})$, and similarly for $g$. Since $2^{b-1}\le 2^b-1 < 2^b$, $$k(2^b-1) = b-1\quad\text{and}\quad k(2^b) = b.$$
If $b$ is even, $b-1$ is odd, so $$ f(2^b-1) = (2^b-1)^{b-1} < (2^b)^{b+1} = f(2^b). $$ If $b$ is odd, $b-1$ is even, so $$ f(2^b-1) = (2^b-1)^{b} < (2^b)^b = f(2^b). $$ This shows that $f$ is increasing. An analogous argument shows $g(2^b-1)< g(2^b)$. $\square$