Solve the recurrence relation f() = f(/2) + 1. I am looking for some feedback/guidance on how to solve this recurrence relation.
$\mathit f(n)$ = $\mathit f \left( \frac n 2 \right) +1$ where $\mathit n=2^{k}$, $\mathit k = 1, 2, 3 . . . $ and $\mathit f(1) = 1$
So far this is what I have, but I am not sure if it is correct. Any hints would be greatly appreciated.
$\mathit f(n)$ = $\mathit f \left( \frac n 2 \right) +1$, $\mathit n=2^{k}$, $\mathit k = 1, 2, 3 . . . $ and $\mathit f(1) = 1$
$\mathit n=2^{k}, n = 2, 4, 8, 16 . . . $
$\mathit f(2)=f(1)+1=1+1=2, k=1, n=2$
$\mathit f(4) = f(2)+1=2+1=3, k=2, n=4$
Thus we can observe that for any value $\mathit k$, we have $\mathit f(n)$ always being $\mathit +1$ greater than $\mathit k$, and thus $\mathit f(n) = k+1$.
Thanks for the help!
 A: Your answer happens to work, but it's not quite rigorous since the pattern you observed, a priori, has no reason to work outside of the cases you checked. 
You can rectify this by proving it works, however, by induction on powers of $2$. That is, assume $f(2^n) = n+1$ and that the recurrence relation holds. 


*

*Verify your explicitly formula $f(2^n) = n+1$ holds for $n=0$ (your given base case)

*Assume the formula holds for $n=k>0$ (your induction hypothesis)

*Show this implies the formula for $n=k+1$ is true (your induction step)


The last step is most of the work, but it is easy to show the induction hypothesis implies it, since
$$f(2^{k+1}) = f(2^k) + 1$$
by our recurrence, but we assume that $f(2^k) = k+1$ by the induction hypothesis, giving
$$f(2^{k+1}) = k+1+1 = k+2$$
which is the result we expect to hold, concluding the induction.
A: $$
f\left(2^{\log_2 n}\right)-f\left(2^{\log_2 \frac n2}\right)=1
$$
or
$$
F(\log_2 n)-F(\log_2 n-1) = 1
$$
now calling $z = \log_2 n$
$$
F(z)-F(z-1)=1
$$
with solution
$$
F(z) = z+C_0
$$
or changing to $f(\cdot)$
$$
f(n) = \log_2 n + C_0
$$
but $f(1) = 1$ then $C_0 = 1$
