I am looking for a function from $\Bbb N^*$ to $\Bbb R^{+*}$
such that $f(n)=f(2n)+f(2n+1)$ (for any $n$ in $\Bbb N^*$).
I also am looking for something smooth, where $f(n+1)-f(n)$ would be strictly decreasing with $n$. A solution like $f(n) = 1/2^{\lfloor \log_2(n)\rfloor}$, for example, isn't ideal as is doesn't decrease smoothly.
My goal is to be able to ponderate values in a specific way such that smaller ones weight more. The whole thing is a bit too complicated to explain here.
I though maybe some kind of exponential could work, but by assuming there are $a$ and $b$ such that $a^nb = a^{2n}b + a^{2n+1}b$ for any $n$ quickly fails.
What else could I try?
Best Answer
Let $g(n) = \log(1+\frac1n)$. Notice
$$1+\frac1n = \frac{n+1}{n} = \frac{2n+2}{2n+1}\frac{2n+1}{2n} = \left(1 + \frac1{2n}\right)\left(1 + \frac1{2n+1}\right)$$ Taking logarithm on both ends, we find $g(n) = g(2n) + g(2n+1)$ and $g(n)$ is a candidate of $f(n)$.
About how I discover such a solution. I look for $f(n)$ which can be expressed as $h(\frac1n)$ where $h(z)$ is real analytic at $z = 0$. The condition $f(n) = f(2n) + f(2n+1)$ suggests $f(n)$ decreases like $\frac{\verb/const/}{n}$ for large $n$. Since the equation is linear, the overall scale of $h$ doesn't matter. I restrict my attention to those $h(z)$ which has expansion of the form:
$$h(z) = z + \sum_{k=2}^\infty \alpha_k z^k\tag{*1}$$
In terms of $h$, the equations $f(n) = f(2n) + f(2n+1)$ becomes
$$h(z) - h\left(\frac{z}{2}\right) - h\left(\frac{z}{z+2}\right) = 0\tag{*2}$$
Using a CAS, I substitute expansion $(*1)$ into $(*2)$ and look for $\alpha_2, \alpha_3, \ldots$ one by one which kills corresponding $z^2, z^3, \ldots$ term in LHS of $(*2)$. I find $\alpha_k = \frac{(-1)^{k-1}}{k}$ for small $k$ and recognize these are the coefficients in a Taylor series expansion of $\log(1+z)$.