$f (1) = 1$ and $f (n) = 2f (⌊\frac n 2⌋ )+1$ for $n \ge 2$. Prove that $f(n) = O(n)$.
So far I've guessed that the solution to the recurrence function is $2^{(\lfloor\log_2 (n)\rfloor)}-1$ and tried to use induction to prove that there exists a constant $C$ such that, for all $n\ge1$, $C\cdot n$ is greater than $2^{(⌊\log_2 (n)⌋)}-1$ to show that $f(n) = O(n)$. However, I'm getting stuck in the induction process because I can't see how to prove $\lfloor \log_2(\lfloor n+1\rfloor)\rfloor = \lfloor \log_2( {\lfloor \frac {n+1} 2\rfloor \cdot2} )\rfloor$. I am open any other ideas on how to prove $f(n) = O(n)$
$$f(n)=2f\left(\left\lfloor\frac n2\right\rfloor\right)+1=4f\left(\left\lfloor\frac n4\right\rfloor\right)+2=\cdots=2^kf\left(\left\lfloor\frac n{2^k}\right\rfloor\right)+k.$$
Hence for
$$2^k\le n<2^{k+1}$$
we have
$$f(n)=2^kf(1)+k<2nf(1)+\log_2n.$$