How to solve a recurrence relation involving a ceiling function?

Question

I have no idea against ceiling function...

How to solve

$f(n) = 2f(\lceil{\frac{n}{2}}\rceil) - 1, n > 2, $
$f(2) = 2$

?

Thanks!

Answer 1

Hint:

$$f(3)=2f(2)-1=3,\\f(4)=2f(2)-1=3,\\f(5)=2f(3)-1=5,\\f(6)=2f(3)-1=5,\\f(7)=2f(4)-1=5,\\f(8)=2f(4)-1=5,\\f(9)=2f(5)-1=9,\\f(10)=2f(5)-1=9,\\f(11)=2f(6)-1=9,\\f(12)=2f(6)-1=9,\\\cdots$$

and a pattern emerges. To make it even more obvious, consider $g(n):=f(n)-1$, and

$$g(3)=2g(2)=2^1,\\g(4)=2g(2)=2^1,\\g(5)=2g(3)=2^2,\\g(6)=2g(3)=2^2,\\g(7)=2g(4)=2^2,\\g(8)=2g(4)=2^2,\\\cdots$$

Answer 2

Hint $$f(n)=2f(1+\lfloor\frac{n}{2}\rfloor)-1$$

Please do tell me how did you solve the rest of problem, as you are able to solve for floor function recurring relation.

Answer 3

Another hint:

Prove by induction that $f(n)$ is constant between one power of $2$ and the next i.e.

$f(n) = f(n+1) \space \forall \space k \ge 1, 2^k < n < 2^{k+1}$

You know that $f(3)=f(4) = 3$ so your base case is $k=1$.

Now you just have to find the value of $f(n)$ at each power of $2$.