Suppose we have a function $f$ such that for positive integers $n \ge1$ and $f(0)=0$ and $f(1)=1$ we have:
i) $f(2n + 1) = 2f(n) + 2$
ii) $f(2n) = f(n) + f(n − 1) + 2$
What is the generating function for $f$, and what is the explicit formula for $f(n)$?
Challenge
Moreover, what would be the value of $\lim_{k \to \infty} \frac{f(2^kx)}{2^kx}$, in terms of $x$