<s>[INST] Proving that $T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)$ 
Show that $T(n)$ is bounded both above and below by $n$ (abusing the Big O notation) for some positive constants $c_1$ and $c_2$:
$$
T(n) = 3T\left(\frac n3\right) + \sqrt n = \Theta(n)
$$

Let's do some substutution for proving first that is $O(n)$. Because $T\left(\frac n3\right) \le c\frac n3$:
$$
\begin{align}
T(n) &= 3T\left(\frac n3\right) + \sqrt n = 3c\frac n3 + \sqrt n\\
&= cn + \sqrt n \le cn
\end{align}
$$
So $cn + \sqrt n \le cn$: where we are adding $\sqrt n$ on the left and pretending that we get something bigger on the right. I would say that $T(n) = \Omega(n)$ for $c \ge 1$, but not $T(n) = O(n)$!
I'm sure that I'm wrong (I have the solution sheet), can you help me find out why?
EDIT: actually I've found a lot of examples where induction does not work, like:
$$
T(n) = 2T\left(\frac n2\right) +1
$$
The technique to solve this (subtract a lower order term from the right side
of the inequality we wish to prove) is explained by Hagen von Eitzen answer. The question remains: why does induction not work in this case?
 [/INST] Suppose the base three representation of $n$ is given by
$$ n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k$$
and we let the base case be $T(0) = 0.$
Then it is not difficult to see that
$$ T(n) = \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j 
\sqrt{\sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}}.$$
Now to get an upper bound on this consider the case of all digits being two, giving
$$ T(n)\le \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j 
\sqrt{\sum_{k=j}^{\lfloor \log_3 n \rfloor} 2\times 3^{k-j}} =
\sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j 
\sqrt{3^{\lfloor \log_3 n \rfloor -j+1}-1} \\ \le
\sqrt{3}^{\lfloor \log_3 n \rfloor+1}
\sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3}^{-j} =
\sqrt{3}^{\lfloor \log_3 n \rfloor+1} 
\sum_{j=0}^{\lfloor \log_3 n \rfloor}\sqrt{3}^j =
\sqrt{3}^{\lfloor \log_3 n \rfloor+1} 
\frac{\sqrt{3}^{\lfloor \log_3 n \rfloor+1}-1}{\sqrt{3}-1}.$$
For a lower bound consider the case of all digits being zero except the first one, giving
$$ T(n)\ge \sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j 
\sqrt{3}^{\lfloor \log_3 n \rfloor-j} = 
\sqrt{3}^{\lfloor \log_3 n \rfloor}
\sum_{j=0}^{\lfloor \log_3 n \rfloor} 3^j \sqrt{3}^{-j} =
\sqrt{3}^{\lfloor \log_3 n \rfloor}
\sum_{j=0}^{\lfloor \log_3 n \rfloor} \sqrt{3}^j \\=
\sqrt{3}^{\lfloor \log_3 n \rfloor}
\frac{\sqrt{3}^{\lfloor \log_3 n \rfloor+1}-1}{\sqrt{3}-1}$$
Finally, taking the leading terms of the upper and the lower bound together, we have shown that
$$ T(n) \in \Theta\left(\sqrt{3}^{\lfloor \log_3 n \rfloor} \times \sqrt{3}^{\lfloor \log_3 n \rfloor}\right) = \Theta\left(3^{\lfloor \log_3 n \rfloor} \right) =
\Theta(n).$$
The next term in the asymptotic expansion is $\sqrt{3}^{\lfloor \log_3 n \rfloor}\sim\sqrt{n}.$
A better upper bound can be found by using the asymptotic expansion of $\sqrt{1-x}$ in a neighborhood of zero, using
$$ \sqrt{3^{\lfloor \log_3 n \rfloor -j+1}-1} \\=
\sqrt{3^{\lfloor \log_3 n \rfloor -j+1}}
\left(1 - \frac{1}{2} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right)
- \frac{1}{8} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right)^2
- \frac{1}{16} \left(\frac{1}{3^{\lfloor \log_3 n \rfloor -j+1}}\right)^3
- \cdots\right).$$
</s>