Functional Equation $ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) $

Question

I have the following functional equation: $$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) $$ Under the precondition that $ f ( n ) = \omega ( 1 ) $, monotonicity and an initial value $ f ( 1 ) = \Theta ( 1 ) $, one can show (by induction) that $ \Omega \big( ( \log n ) ^ k \big) = f ( n ) = O ( n ^ \alpha ) $ for arbitrary large $ k $ and small $ \alpha $ (see below).

It seems to me that these bounds are very tight so the question is:

Is there a (simple) function that satisfies these conditions?

---

Proof sketch:

$$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) \le 2 \left( \frac n { f ( n ) } \right) ^ \alpha = \left( \frac 2 { f ( n ) ^ \alpha } \right) n ^ \alpha \le n ^ \alpha $$ for sufficiently large $ n $.

$$ f ( n ) = 2 f\left( \frac n { f ( n ) } \right) \ge 2 \left( \log \frac n { f ( n ) } \right) ^ k \ge 2 \left( \log \frac n { n ^ \alpha } \right) ^ k = 2 ( 1 - \alpha ) ^ k ( \log n ) ^ k \ge ( \log n ) ^ k $$ for sufficiently large $ n $ and small $ \alpha $.

Answer 1

Hint:

$f(n)=2f\left(\dfrac{n}{f(n)}\right)$

$\dfrac{f(n)}{f\left(\dfrac{n}{f(n)}\right)}=2$

$\dfrac{\dfrac{n}{f(n)}}{f\left(\dfrac{n}{f(n)}\right)}=\dfrac{2n}{(f(n))^2}$

Let $g(n)=\dfrac{n}{f(n)}$ ,

Then $g(g(n))=\dfrac{2(g(n))^2}{n}$

Answer 2

First of all, note that for a nonnegative constant $ c $, the function $ f $ defined by $$ f ( n ) = 2 ^ { - \frac 1 2 + \sqrt { 2 \log _ 2 n + c } } $$ satisfies the functional equation $$ f ( n ) = 2 f \left( \frac n { f ( n ) } \right) \text . $$ Also, $ f $ is strictly positive and strictly increasing, and as $ n \to + \infty $, $ f ( n ) \in o ( n ^ \alpha ) \cap \omega \big( ( \log _ 2 n ) ^ k \big) $ for any $ k $ and any positive $ \alpha $.

But how can one find such solutions? For more simplicity in the upcoming calculations, first define the function $ g $ with $ g ( n ) = \log _ 2 f ( 2 ^ n ) $, so that we have $ f ( n ) = 2 ^ { g ( \log _ 2 n ) } $. Then, the functional equation is simplified to $$ g ( n ) = g \big( n - g ( n ) \big) + 1 \text . $$ Assuming we have $ g ( n ) = m $ for some fixed $ n $, using induction we get $$ g \left( n - m k + \frac { k ( k - 1 ) } 2 \right) = m - k $$ for any nonnegative integer $ k $. Assuming that $ f $, and thus $ g $, is well-behaved enough, we can consider the above equation for all nonnegative real values of $ k $. By letting $ y = m - k $ and $ x = n - m k + \frac { k ( k - 1 ) } 2 $, we can see that $$ m - y = k = m + \frac 1 2 \pm \sqrt { \left( m + \frac 1 2 \right) ^ 2 - 2 ( n - x ) } \text , $$ which for $ y > 0 $ gives $$ g ( x ) = y = - \frac 1 2 + \sqrt { 2 x + c } \text , $$ where $ c = \left( m + \frac 1 2 \right) ^ 2 - 2 n $. This holds for any $ x \le n $, as we had the previous equations for any $ k \ge 0 $. Thus, we can see that $ \left( g ( x ) + \frac 1 2 \right) ^ 2 - 2 x $ is in fact constant on the whole domain (the constant must be nonnegative if we want the square root above to be well-defined for all positive values of $ x $). Therefore, the above formula for $ g ( x ) $ holds for any desired input, and writing it in terms of $ f $ gives the claimed result for all $ n \ge 1 $.