Find non-smooth function that meets conditions I learned the following theorem in class:
"If $T(n)$ is asymptotically non-decreasing and $f(n)$ is smooth, then $T(n) =
O(f(n)|n=b^k, k=integer)$ implies $T(n) = O(f(n))$."

I'm trying to show using a counterexample that this theorem doesn't hold if $f(n)$ is non-decreasing but not smooth. Smoothness means that $f(bn) = O(f(n))$.

From my understanding, the above conditions mean that $f(n)$ must be an exponential. Other than that, how would I go about finding a function that meets the conditions outlined above?

Since this is a homework problem, please don't give an actual function, but instead give a series of steps to take to find the function. Thanks.
As you mention, the function $f(n)$ needs to grow fast, though not necessarily exponentially fast ($n^{\log n}$ also works, for example). Nevertheless, let's take your suggestion $f(n) = 2^n$ for definiteness. Simplifying things a bit, you are looking for a function $T(n)$ such that


$T(n)$ is non-decreasing.
$T(2^k) = 2^{2^k}$.
$T(n)$ is not $O(2^n)$.


To satisfy the third condition, we would like $T(n)$ to be "as large as possible" given the first two conditions.


  (a) Find the function $T(n)$ which is "as large as possible" subject to the first two conditions.
  
  (b) Show that it satisfies the third condition as well.
  
  (c) For which functions $f(n)$ does this construction work?