Solve the recurrence relation f() = f(/2) + 1.

Question

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!

Answer 1

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.

Answer 2

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