How to prove $T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$ is $\mathcal O(n\log n)$ using induction? How would you go about proving the recursion 
$$T(n) = T\left(\frac n4\right) + T\left(\frac{3n}4\right) + n$$is $\mathcal O(n\log n)$ using induction?
Thanks!
 A: $$
T(n)=T(n/4)+T((3n)/4)+n
$$
is a linear difference equation which can be solved as
$$
T(n) = T_h(n) + T_p(n)\\
T_h(n) = 0\\
T_p(n) = T_p(n/4)+T_p((3n)/4)+n
$$
Now making 
$$
T_h(n) = a^{\ln n} = e^{\lambda \ln n} = e^{\ln n^{\lambda}} = n^{\lambda}
$$
we have
$$
n^{\lambda} = \left(\frac{n}{4}\right)^{\lambda}+\left(\frac{3n}{4}\right)^{\lambda}
$$
or
$$
4^{\lambda} = 1 + 3^{\lambda}\Rightarrow \lambda = 1 =\ln a \Rightarrow a = e \Rightarrow T_h(n) = n
$$
etc.
A: I will assume that we are using the "floor" function, i.e. that $n/4$ and $3n/4$ denote the integral part of the quotient. With this convention, $T(19)=T(4)+T(12)+19$. Note that it is easy to tweak the proof to adapt to other cases.
Let $$M=\max \left\{\frac{T(2)}{2\log(2)},\frac{T(3)}{3\log(3)},\dots,\frac{T(7)}{7\log(7)},\frac{4}{\log(256/27)} \right\},$$
we will prove that $T(n) \leq M n \log n$ for all $n\geq 2$. (We must exclude $n=1$ since $T(1)$ can never be made smaller than a multiple of $1 \log 1 = 0$.)
The constant $M$ might look a bit scary, but it is simply crafted so that $T(n) \leq M n \log(n)$ for $2\leq n \leq 7$, and so that $M\geq \frac{4}{\log(256/27)}$, which we will see later is the crux of the proof.
Let us use strong induction to prove the result. The initialization step is trivial for $2\leq n \leq 7$, since we have constructed $M$ such that $T(n)\leq Mn\log n$ in these cases. For the induction step, let $n\geq 8$ be some integer, and let us assume that we have $T(k)\leq Mk\log k$ for all $2\leq k<n$.
We will first assume that $n$ is a multiple of $4$, since this is the easiest case. Denote $n=4m$, with our floor function convention we have $T(4m)=4m+T(m)+T(3m)$. Since $n\geq8$, $m\geq2$ and we can therefore use the induction hypothesis for $m$ and $3m$ to write:
$$\begin{eqnarray}T(n) = T(4m) &\leq& 4m + Mm\log m + M.3m\log(3m) \\
&=& 4m + Mm\log (4m) - Mm\log4 + M.3m\log (4m) - M.3m\log(4/3) \\
&=& 4m + M.4m\log (4m) - Mm\log(4\times(4/3)^3) \\
&=& M.4m\log (4m) + m(\underbrace{4 - M\log(256/27)}_{\leq 0}) \\
&\leq& M.4m\log(4m) = Mn\log n
\end{eqnarray}$$
Now, if $n$ is not a multiple of $4$, let us write $n=4m+k$ with $k \in \{1,2,3\}$. In this case we have $T(n)=T(m)+T(3m)+(4m+k)=T(4m)+k$, thus we can simply re-use what we just proved for $4m$:
$$\begin{eqnarray}T(n) = T(4m+k) &=& T(4m)+k \\
&\leq& M.4m\log(4m) + k\times \underbrace{1}_{\leq M\log(4m)} \\
&\leq& M.4m\log(4m) + k.M\log(4m) = (4m+k)\log(4m) \\
&\leq& M(4m+k)\log(4m+k) = Mn\log n
\end{eqnarray}$$
