How to work out the odd case?

I am trying to solve this by using Substitution method. My solution must work both for even n-s and odd n-s. For evens case I have solved it. But for the odd's case I am stuck at this point. Hot to continue?

• You say that you want to solve the recurrence using the Master theorem, but then your proof is by induction. Which of the two is it? Besides your proof is incomplete (no base case, no choice of $c$). Feb 21, 2021 at 13:45
• @Steven I am sorry. I wanted to write Substitution method. Feb 21, 2021 at 13:53
• If $n$ is even, then $\frac n2-\frac12$ is not integer ! By the way, having a solution fir even $n$ is far from being sufficient, because $\frac n2$ might very well be odd.
– user16034
Mar 18, 2022 at 19:41

If you have a solution for all even numbers, it might be sufficient to realize $$T(k+1) \ge T(k)$$.
If $$n$$ is even then
$$T(n)=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n$$ and
$$T(n+1)=2T\left(\left\lfloor\frac{n+1}2\right\rfloor\right)+n+1=2T\left(\left\lfloor\frac n2\right\rfloor\right)+n+1=T(n)+1>T(n).$$