# 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$). – Steven Feb 21 at 13:45
• @Steven I am sorry. I wanted to write Substitution method. – Diana Feb 21 at 13:53

## 1 Answer

If you have a solution for all even numbers, it might be sufficient to realize $$T(k+1) \ge T(k)$$.

But generally this is proved by induction where the even numbers use the odd ones. There, you have two leads :

• Take good care of your bounds during your induction
• More simple (but with less efficient approximation) : prove it for powers of two with a given constant ; and then use those to prove the general case for another constant