Solving an unrelated problem I have found the following recursion: $$g(k)=\begin{cases}4g\left(\frac k2\right)&k\text{ even}\\ 2g\left(\lfloor\frac k2\rfloor\right) + 2g\left(\lceil\frac k2 \rceil\right)&k\text{ odd}\end{cases}$$ with initial condition $g(1)=1$. I managed to prove that $g(k)\geq k^2$ for all $k$. Also I managed to prove that $g(k)\leq k^3$ (actually I found out that the exponent can be smaller than three). I'm trying to find the solution of the recurrence, this definition for $g(k)$ may be the solution but I cannot prove that it fulfills the recursion:
$$g(k) = 3k2^{\lfloor\log_2 k\rfloor} - 2^{1+2\lfloor\log_2 k\rfloor}$$ Could someone help me proving that it is indeed the solution (or otherwise that it is not and the solution is another one)