Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem
Throughout this answer, we assume $f$ and $T$ are non-negative. Our proof works whenever $f = \Theta(g)$ for some monotone $g$. This includes your Mergesort example, in which $f=\Theta(n)$, and any function which has polynomial growth rate (or even $\Theta(n^a \log^b n)$).
Let's consider first the case that $f$ is monotone non-decreasing (we'll relax this assumption later). We concentrate on your sample recurrence
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n). $$
This recurrence needs two base cases, $T(0)$ and $T(1)$. We make the assumption that $T(0) \leq T(1)$, which we also relax later on.
I claim that $T(n)$ is monotone non-decreasing. We prove by complete induction that $T(n+1) \geq T(n)$. This is given for $n = 0$, so let $n \geq 1$. We have
$$
\begin{align*}
T(n+1) &amp;= T(\lfloor (n+1)/2 \rfloor) + T(\lceil (n+1)/2 \rceil) + f(n+1) \\
&amp;\geq T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + f(n) = T(n).
\end{align*}
$$
This implies that
$$ T(2^{\lfloor \log_2 n \rfloor}) \leq T(n) \leq T(2^{\lceil \log_2 n \rceil}). $$
So if $T(2^m) = \Theta(T(2^{m+1}))$, we're done. This is always the case if the solution for powers of two is of the form $T(n) = \Theta(n^a \log^b n)$.
Now let's relax the assumption that $T(0) \leq T(1)$. Consider a new recurrence $T'$ defined in exactly the same way, only $T'(0) = T'(1) = \min(T(0),T(1))$. We can prove by induction that $T'(n) \leq T(n)$. Similarly, we can define a new recurrence $T''$ satisfying $T''(0) = T''(1) = \max(T(0),T(1))$, and then $T(n) \leq T''(n)$. Invoking the Master theorem, we see that $T'=\Theta(h)$ and $T''=\Theta(h)$ for the same function $h$, and so $T = \Theta(h)$ as well.
Now let's relax the assumption that $f$ is monotone. Suppose that $f = \Theta(g)$ for some monotone function $g$. Thus $cg(n) \leq f(n) \leq Cg(n)$ for some $c,C&gt;0$ and $n$ large enough. We assume for simplicity that $n=0$; the general case can be handled as in the previous paragraph. Again we define two recurrences $T',T''$ by replacing $f$ with $cg,Cg$ (respectively). Once again the Master theorem will give the same result (up to constant multiples), which is also identical (up to constant multiples) to what we would get by solving the original recurrence only on powers of two.