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$?
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.