# Functional Equation $f(n) = 2 f(n / f(n) )$

I have the following functional equation:

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

Under the precondition that $f(n) = \omega(1)$, monotinic and a initial value $f(1) = \Theta(1)$ one can show (by induction) that $\Omega((\log n)^k) = 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 \cdot f\left(\frac{n}{f(n)}\right) \le 2 \cdot \left(\frac{n}{f(n)}\right)^\alpha = n^\alpha \cdot \left(\frac{2}{f(n)^\alpha}\right) \le n^\alpha \quad$ for sufficient large $n$.

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

• Is your function defined on integers? Then I don't understand what $\frac{n}{f(n)}$ means. $f(n)$ is always a divisor of $n$? But then by your equation either $f(p)=2f(1)$ if $f(p)=p$ or $f(p)=2f(p)$ if $f(p)=1$... – user68061 Jan 13 '14 at 18:28
• @user68061 Given the way the function is written, I don't think assuming it is defined for the integers is reasonable (granted, the OP is using the variable $n$...) – Igor Rivin Jan 13 '14 at 18:32
• Well, then what is meant by proof by induction''? – user68061 Jan 13 '14 at 18:33
• the functional equation in the title is not the same as in the post ... – kjetil b halvorsen Jan 13 '14 at 19:13
• @kjetilbhalvorsen Thanks. $f(n) = f(n)/2 + f(n/f(n))$ was the original (equivalent) form. It's now simplified in the title, too. – Hannes Jan 13 '14 at 20:02

$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}$