Is there an increasing function which satisfies $f(1) = 3$ and $f(f(n)) = f(2n)+ 1$ for all natural numbers?
I first tried doing this problem using the subbing values, by subbing values of $n=-1,0,1$, but I was not able to prove anything relating to strictly increasing, because I kept ending up at the same looped conclusion.
I did try $n=1/2$, and from $f(2n)+1$, it can be found that $f(f(n))=4$, but I am not too sure where to go on from here.
Any help is appreciated!
No, no such a function exists.
Let’s try to find it. Note that because $f(f(n)) = f(2n) + 1 > f(2n)$ and $f$ is increasing, we have $f(n) > 2n$.
We also have $f(f(n)) = f(2n) + 1 \leq f(2n + 1)$, and since $f$ is strictly increasing, this means $f(n) \leq 2n + 1$.
Therefore, $f(n) = 2n + 1$. We have found the only possible candidate, so let’s take that to be the definition of $f$ and see if it works.
Let’s plug this into our function equation. We get $2(2n + 1) + 1 = 2(2n)+ 1 + 1$. Unfortunately, this equality fails.