Given $f: \mathbb N \to \mathbb N$ such that $$2f(n)f(2n+1)=f(2n)(2f(n)+1)$$ and $$8f(n)>f(2n)>4(f(n)$$ Find $f(12)$ in terms of $f(1)$
Options:
1.$6^3 f(1) + 108$
2.$6f(1)+9$
3.$6^2f(1) +6$
4.$f(1) +108$
I tried putting in the values but couldn't figure out how to extract $f(12)$ out of it. Is there anyway to find any function $f(n)$ satisfying this? I also tried eliminating $f(2n+1)$ but couldn't. Any help would be appreciated. Thank you!
On
Here's an explicit description of all values $f(n)$ in terms of $f(1)$:
Claim: If $n=\sum_{i=0}^ma_i2^i$ with $a_i\in\{0,1\}$ and $a_m=1$, then $$\tag1 f(n)=6^mf(1)+3\sum_{i=0}^{m-1}a_i6^i$$ Proof: From the functional equation, we find that using $\gcd(2f(n),2f(n)+1)=1$ that $2f(n)\mid f(2n)$. Then with $4f(n)<f(2n)<8f(n)$, we conclude $$\tag2 f(2n)=6f(n).$$ Moreover, $$\tag3f(2n+1)=\frac{f(2n)(2f(n)+1)}{2f(n)}=3(2f(n)+1)=f(2n)+3.$$ Note that $(2)$ and $(3)$ uniquely determine all $f(n)$ in terms of $f(1)$. Hence for a proof of the claim by induction, it suffices to show that the right hand side of $(1)$
The first is trivial. The second follows because doubling increases $m$ by $1$ and pushes all $a_i$ one up. The third follows because the only change is that $a-0$ switches from $0$ to $1$. $\square$
In particular, $$f(12)=f(1100_2)=6^3f(1)+3\cdot 6^2.$$
Put $n=1$ in the given equation. You get $$(*)\ 2f(1)f(3)=f(2)(2f(1)+1)$$ Hence $f(2)$ is even: $f(2)=2k$ for some natural $k$. We get $f(1)f(3)=k(2f(1)+1)$ and, since $x$ and $2x+1$ are relatively prime, $f(1)$ must divide $k$.
Let $k=lf(1)$, $l\in\mathbb{N}$. From $8f(1)>f(2)>4f(1)$ we have $8f(1)>2lf(1)>4f(1)$, that is $4>l>2$, hence $l=3$, so we proved that $f(2)=6f(1)$.
Now, from $(*)$ you get $f(3)=6f(1)+3$.
Can you make a next step yourself now?