Prove that $f(x)\leq x\cdot\log_2 x$ for all integer $x\geq1$

Question

Let $f$ be a function which satisfies that $f(x) = \left \{ \begin{matrix} 0 & \mbox{for }x=1 \\ 2\cdot f(\frac{x}{2})+x, & \mbox{for }x\geq1 \end{matrix} \right.$

Prove that $f(x)\leq x\cdot\log_2 x$ for all integer $x\geq1$

Answer 1

This is fun. Ok set let $k = log_2 x$, i.e. $2^k = x$. (Currently in the definition we can only compute $f(x)$ on $x$ which are powers of 2.

Now this means when we are applying our halvings to $x$ in $f$, we are allowed to do it $k$ times. Of course, $f(1)=0$, this will make our inequality work.

I will do the first few terms for you and see if you can spot a pattern.

$f(x) = 2f(x/2)+x$ $f(x) = 2(2f(x/4)+x/2)+x = 2^2 f(x/4) + 2x$

…

So think of what the term involving $f(x/(2^k)) = f(1) = 0$ would be.