0

Given that $f(1) = 1$ and for $n\geq1$, $$f(2n) = f(2n + 1) = 2f(n)$$ show that for every natural number $n$, $f(n)$ is the largest power of $2$ less than or equal to $n$.

I don't understand what is going on. Am I asked to prove that $f(n) = 2^{k}$ and $k\leq n$?

Deniz Cetinalp
  • 829
  • 1
    Not exactly. You are asked to show that for all $n$, we have $f(n)=2^k$ for some $k$, and that (1) We have $f(n)\le n$ for all $n$ but (2) We also have $n<2f(n)$ for all $n$. A natural approach to a problem like this is to use (strong) induction, considering cases according to whether $n$ is even or odd. – Andrés E. Caicedo Sep 23 '13 at 22:20

1 Answers1

2

Try a few values to see if you can see a pattern: $$ \begin{array}{c|c} k&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline f(k)&1&2&2&4&4&4&4&8&8&8&8&8&8&8&8&16 \end{array}\tag{1} $$ The pattern seems to be $$ f(k)=2^{\lfloor\log_2(k)\rfloor}\tag{2} $$ Looking at $(1)$, we have that $(2)$ holds for $k=1$.

For $n>1$, assume that $(2)$ holds for all $k\lt n$ and see if we can show that it holds for $k=n$.

If $n$ is even, since $n/2<n$, we have $$ \begin{align} f(n) &=2f(n/2)\\ &=2\cdot2^{\lfloor\log_2(n/2)\rfloor}\\ &=2\cdot2^{\lfloor\log_2(n)\rfloor-1}\\ &=2^{\lfloor\log_2(n)\rfloor}\tag{3} \end{align} $$ and therefore, $(2)$ holds.

If $n$ is odd, since $(n-1)/2<n$, we have $$ \begin{align} f(n) &=2f((n-1)/2)\\ &=2\cdot2^{\lfloor\log_2((n-1)/2)\rfloor}\\ &=2\cdot2^{\lfloor\log_2(n-1)\rfloor-1}\\ &=2^{\lfloor\log_2(n-1)\rfloor}\\ &=2^{\lfloor\log_2(n)\rfloor}\tag{4} \end{align} $$ and therefore, $(2)$ holds.

robjohn
  • 345,667