How to solve a recurrence relation involving a ceiling function?

1,115

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

Solution 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.

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

Share:
1,115

Related videos on Youtube

OOD Waterball
Author by

OOD Waterball

Updated on August 01, 2022

Comments

  • OOD Waterball
    OOD Waterball over 1 year

    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!

    • Matti P.
      Matti P. almost 5 years
      Idea: split $n$ to even and odd numbers. If $n$ is odd, $f_{n+1}$ should be the same as $f_{n}$.
    • Sil
      Sil almost 5 years
      Write first couple values, notice a pattern, try to prove the pattern...
  • OOD Waterball
    OOD Waterball almost 5 years
    Oops, I meant I can solve $f(n) = {f(\lfloor\frac{n}{2}\rfloor)} + 1$ by seeing it as shifting right $n$ in a form of binary numbers. But the one you gave me is out of my ability I just noticed.
  • Lakshya Sinha
    Lakshya Sinha almost 5 years
    Yeah I tried it's difficult even from my side :-)
  • OOD Waterball
    OOD Waterball almost 5 years
    By observing, I would write $f(n) = 2^{\lceil\log_2 n\rceil - 1} + 1$. Thanks for the hint! I wonder if there are some procedures dealing with ceiling recurrence rather than observing the pattern?
  • Admin
    Admin almost 5 years
    @OODWaterball: you can temporarily ignore the floor/ceiling and solve. This usually yields an asymptotically correct solution. In this case, you can solve for $n=2^k$, then use monotonocity arguments to generalize to arbitrary $n$.