0

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$

Yanko
  • 13,758
Cicero Samuel
  • 3
  • 3
  • 1
    I edit your question. There's a huge problem with the definition of $f$ (you define $f$ using $f$). Can you fix that? and at the same time make sure that my edits are appropriate. – Yanko Apr 04 '19 at 15:43
  • Thanks. Your edits are correct. But the question do defines f using f, I don't know how to fix that. – Cicero Samuel Apr 04 '19 at 15:50
  • I edit your question again to make that part clear. – Yanko Apr 04 '19 at 15:52
  • 1
    This definition is not complete. For example, try to evaluate $f(3)$. It should be $2f(1.5)+3$. And $f(1.5)$ is $2f(0.75)+1.5$. But there is no rule how to compute $f(0.75)$. Maybe the first rule holds for all $x\le1$ – Saša Apr 04 '19 at 16:24
  • Agree, can only do it for powers of 2 – fGDu94 Apr 04 '19 at 16:42

1 Answers1

0

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.

fGDu94
  • 3,916