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?
 A: You are given $T(n) = 3 T(n/3) + \sqrt{n}$ and want to prove that $T(n) = O(n)$.
Your induction assumption: there is some $c$ such that $T(k) \le ck$ for all $k < n$. Fine so far.
Now you are trying to use the recurrence:
$T(n) = 3 T(n/3) + \sqrt{n} \le cn + \sqrt{n}$
Thus if, $T(n/3) \le cn/3$ then $T(n) \le cn + \sqrt{n}$
Note that this only shows an upper bound on $T(n)$, given the upper bound on $T(n/3)$.
This does not contradict the fact that $T(n) \le cn$
This only means that the upper bound assumption you started with: $T(n/3) \le cn/3$, though true, was not sufficient for your purposes and you need to pick a stronger hypothesis. 
(One explanation this happens is that not all functions in $O(n)$ satisfy $T(n) \le 3T(n/3) + \sqrt{n}$. The induction proof you are trying to apply applies to all functions in $O(n)$)
That is one reason you need to consider the lower order terms.
For instance, if you assume that $T(k) \le ck - 2\sqrt{k}$, then I believe the induction proof goes through.
A: Show that $T(n) = O(n-\sqrt n)$ and then use $n-\sqrt n=O(n)$:
If $T(\frac n3)<c\left(\frac n3-\sqrt{\frac n3}\right)$ then 
$$\begin{align} T(n)&= 3T(\frac n3)+\sqrt n\\&< cn-c\sqrt 3\sqrt n+\sqrt n \\&= cn - (c\sqrt 3-1)\sqrt n\\
&\le c(n-\sqrt n)\end{align}$$
provided $c\sqrt 3-1\ge c$, i.e. $c\ge \frac1{\sqrt 3-1}$.
A: You're correct to be skeptical about the substitution you've employed - because you started with a presumed constant $c$ for your equation $T(n)\in O(n) \implies T(n)\leq cn$ and then showed that the fact that that constant worked for $\frac{n}{3}$ doesn't imply that the same constant works for $n$.  But that doesn't mean that it's impossible that any constant works; it just means that a finer analysis is required.
Instead, for a problem like this it's better to substitute $n=3^t$ and recast $T(n) = T(3^t) = U(t)$; then the equation becomes $U(t) = 3U(t-1) + 3^{t/2}$.  From here, we can expand recursively:
$$\begin{array}
\\
U(t) &= 3\left(3U(t-2)+3^{(t-1)/2}\right)+3^{t/2} \\
&= 3^2 U(t-2) + 3^{(t+1)/2} + 3^{t/2} \\
&= 3^2\left(3U(t-3)+3^{(t-2)/2}\right) + 3^{(t+1)/2} + 3^{t/2} \\
&= 3^3U(t-3) + 3^{(t+2)/2}+3^{(t+1)/2}+3^{t/2} \\
&\ldots \\
&= 3^tU(0) + \sum_{i=t}^{2t-1}3^{i/2} = 3^tU(0) + 3^{t/2}\sum_{i=0}^{t-1} 3^{i/2}
\end{array}$$
Now,from here you should be able to sum the geometric series and find a value for $U(t)$; once you have that, you can plug back in $3^t=n$ and find an inequality for $T(n)$.
A: 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).$$
