I have the following function:
$$f(n) = \begin{cases} k,& n = 1 \\ 2f\left(\left\lfloor\dfrac n2\right\rfloor \right)+1, & n > 1 \end{cases}$$ I have to prove that for every $k>0$ we get $f(n)=\Theta(n)$.
So I managed to prove that $f(n)=O(n)$, but I'm having trouble proving the lower bund. I tried to claim $f(n)\geq0.5kn$ for all $k>0$ using induction. base case would be $k=1$ so $f(1)=k\geq0.5k$ and then after assuming the induction hypothesis the step will be: $f(n)=2f(\left \lfloor \frac{n}{2} \right \rfloor)+1\geq 2(0.5k\cdot\lfloor \frac{n}{2}\rfloor)+1\geq k\cdot\lfloor \frac{n}{2}\rfloor+1\geq k\frac{n}{2}$
but I suppose the last step is illegal since adding 1 to floor of n/2 won't necessarily be greater than 1. thanks in advance.!
We want a bound of the form $f(n)\ge An$ and will use $\lfloor x\rfloor>x-1$ to get rid of the floor function. So the induction step looks like: $$ \begin{align} f(n) &=2f\left(\left\lfloor \frac n2\right\rfloor\right)+1\\ &\ge2A\left\lfloor \frac n2\right\rfloor+1\\ &>2A\left(\frac n2-1\right)+1\\ &=An+1-2A\\ &\ge An \end{align} $$ where the last step works as long as $A\le\frac12$. For the base case, you need $A\le k$, so take $A=\min(k,\frac12)$.
Alternatively, an exact solution is $f(n)=2^{\lfloor\log_2n\rfloor}(k+1)-1$. This formula can be proved straightforwardly by induction, using that $\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor+1=\lfloor\log_2n\rfloor$. To see this fact, let $r=\lfloor\log_2n\rfloor$ so that $n\in[2^r,2^{r+1})$, so $\frac n2\in[2^{r-1},2^r)$, so in fact $\left\lfloor\frac n2\right\rfloor\in[2^{r-1},2^r)$, so $\left\lfloor\log_2\left\lfloor\frac n2\right\rfloor\right\rfloor=r-1$.
Then it's clear that $f$ is $\Theta(n)$, since $\frac {n+1}2\le2^{\lfloor\log_2 n\rfloor}\le n$, and each $\le$ is actually an equality for infinitely many $n$. The graph of $f$ consists of horizontal lines through the region bounded by the lines $y=(k+1)\frac{x+1}2-1$ and $y=(k+1)x-1$.