[Math] How to solve a recurrence relation involving a ceiling function

ceiling-and-floor-functionsrecurrence-relations

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!

Best Answer

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

Related Question