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!

Chairman Meow
  • 796
  • 1
  • 8
  • 24

2 Answers2

2

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.

PrincessEev
  • 43,815
  • Ah I see. I will do that then, that is clear enough. My next thought was to see if there was something else that could be said if you notice that you can express k as $\mathit k=$ $\mathit ln(n)\over ln(2)$. – Chairman Meow Nov 25 '19 at 05:50
1

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

Cesareo
  • 33,252