Looking for function which satisfies $f(n)=f(2n)+f(2n+1)$

Question

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?

Answer 1

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)$.

Answer 2

Suppose we knew the value of $f$ at $1$ and all the positive even integers, then we'd know $f$ everywhere, since $f(3)=f(1)-f(2)$ and $f(5)=f(2)-f(4)$ and $f(7)=f(3)-f(6)$ and so on. This is formalized in the following theorem:

Theorem 1: Let $A$ be an abelian group,let $g:\mathbb{Z}_{\ge 1}\to A$ be a function, and $a\in A$ an element. Then there exists a unique function $f:\mathbb{Z}_{\ge 1}\to A$ which satisfies $$ f(1)=a\quad\text{and}\quad f(n)=f(2n)+f(2n+1)\quad\text{and}\quad f(2n)=g(n) $$ for all $n\in\mathbb{Z}_{\ge 1}$.

Proof: For all $m\ge 0$, define $S_m:=\left\{2n+1:0\le n\le m\right\}\cup\{2n:n\ge 1\}$. Define $f_0:S_0\to A$ by $f_0(1):=a$ and $f_0(2n):=g(n)$ for all $n\ge 1$. For all $m\ge 1$, define $f_m:S_m\to A$ as follows. For all $x\in A_m$ with $x\in A_{m-1}$, we take $f_m(x):=f_{m-1}(x)$. If $x\not\in A_m$, then $x=2m+1$ and $2m,m\in A_m$, so we can safely set $f_m(2m+1):=f_m(m)-f_m(2m)$.

Claim: For all $N\ge 1$ and all $1\le n\le N$, we have $$f_N(2n+1)=f_N(n)-f_N(2n).$$

Proof of Claim: Exercise. Use induction over $N$.

Claim: Let $f:\mathbb{Z}_{\ge 1}\to A$ be a function satisfying $f(1)=a$ and $f(2n)=g(n)$ for all $n\ge 1$. Then $f(2n+1)=f(n)-f(2n)$ for all $n\ge 1$ if and only if $f(2n+1)=f_n(2n+1)$ for all $n\ge 1$.

Proof of Claim Exercise. Use induction over $n$ for the 'only if' part.

$\square$

---

From Theorem $1$, we see that if we were looking for $f:\mathbb{Z}_{\ge 1}\to \mathbb{R}$, that is if negative values were allowed, then we could freely pick $f(1)$ and $f(2n)$ for all $n\ge 1$, and this would uniquely determine $f$.

However, you want the domain to be $\mathbb{R}_{>0}$. Obviously we could just pick $f$ to be positive at $1$ and all positive even integers and apply Theorem $1$ to construct $f$, but this doesn't guarantee anything about the values of $f$ at the odd integers at least $3$. We want $f(2n+1)>0$, or equivalently $f(n)>f(2n)$, for all $n\ge 1$.

Lemma 2: Let $f:\mathbb{Z}_{\ge 1}\to \mathbb{R}$ be a function which satisfies $f(n)=f(2n)+f(2n+1)$ for all $n\in\mathbb{Z}_{\ge 1}$. Then the following are true:

• $f(2^m-1)=f(1)-\sum_{n=2}^mf(2^n-2)$ for all $m\ge 1$
• $f(2^{k+1}m+2^{k}-1)=f(2m)-\sum_{n=1}^kf(2^{n+1}m+2^n-2)$.

Proof: Exercise. Again, use induction. $\square$

Note that all odd positive integers are of one of the two forms mentioned in the Lemma. This leads immediately to the following theorem:

Theorem 3: Let $g:\mathbb{Z}_{\ge 1}\to\mathbb{R}_{>0}$ be a function and $a\in\mathbb{R}_{>0}$ a constant. Then there exists a function $f:\mathbb{Z}_{\ge 1}\to\mathbb{R}_{>0}$ which satisfies $$ f(1)=a,\quad f(n)=f(2n)+f(2n+1)\quad\text{and}\quad f(2n)=g(n) $$ for all $n\in\mathbb{Z}_{\ge 1}$ if and only if $$ a>\sum_{n= 1}^\infty g(2^{n}-1)\quad\text{and}\quad g(m)>\sum_{n=1}^\infty g(2^{n}m+2^{n-1}-1) $$ for all integers $m\ge 1$. Moreover, this $f$ is unique if it exists.

Proof: Exercise. Use Lemma $2$. $\square$

---

Theorem $2$ essentially requires that for all $n$ the sequence $g(n),g(2n+1),g(4n+3),g(8n+7),\ldots$ decreases extremely rapidly -- each term has to be larger then the sum of all the terms that follow it.