Need some help with this recurrence equation I'm self studying from a book I bought to learn more about algorithms and I've been trying most of the exercises in that book, so this is not a homework. Anyways, the relation I'm trying to solve is 
$$
T(n)=T(n/2)+T(n/4)+T(n/8)+n
$$
I need to find a good asymptotic upper and lower bounds.
So, far what I've done is to transform the above considering $n=2^m$ then
$$
T(2^m)=T(2^{m-1})+T(2^{m-2})+T(2^{m-3})+2^m
$$
then for $S(m)=T(2^m)$
$$
S(m)=S(m-1)+S(m-2)+S(m-3)+2^m
$$
using the recursion tree with this later equation is a lot easier but I'm still not able to get to the solution.
Hope I'm on the right path :)
 A: Technically the recurrence should use $\lfloor \frac{n}{2} \rfloor$ instead of $\frac{n}{2}$ (or ceiling, depending on the context), so that it is properly defined. It will look like this:
$$T(n)=T\left(\left \lfloor \frac{n}{2} \right \rfloor \right)+T\left(\left \lfloor \frac{n}{4} \right \rfloor \right)+T\left(\left \lfloor \frac{n}{8} \right \rfloor \right)+n$$
Typically, when analysing asymptotic behaviour, we can ignore the floors. (which gives $O(1)$ error) We extend $T(n)$ to $[0, \infty)$ with $T(n)=T(\lfloor n \rfloor)$. We now get back the equation you have:
$$T(n)=T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+n$$
Now, I shall show that $T(n)=8n+O(n^\theta)$, where $\theta \approx 0.87915$ is the only real root of $\left(\frac{1}{2}\right)^{\theta}+\left(\frac{1}{4}\right)^{\theta}+\left(\frac{1}{8}\right)^{\theta}-1=0$. 
Indeed, if we subtract $8n$ from both sides of the above equation, we get:
$$(T(n)-8n)=(T\left(\frac{n}{2}\right)-\frac{8n}{2})+(T\left(\frac{n}{4}\right)-\frac{8n}{4})+(T\left(\frac{n}{8}\right)-\frac{8n}{8})$$
If we let $U(n)=T(n)-8n$, then
$$U(n)=U\left(\frac{n}{2}\right)+U\left(\frac{n}{4}\right)+U\left(\frac{n}{8}\right)$$
Suppose that for $1 \leq n \leq 8$, we have $an^{\theta} \leq U(n) \leq bn^{\theta}$, for some constants $a, b$. Indeed, we have 
$$\min_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-64 \leq U(n)=T(n)-8n \leq \max_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-8$$
If we let $a=\min(0, \min_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-64), b=\max(0, \max_{1 \leq i \leq 8, i \in \mathbb{Z}}{T(i)}-8)$, then $an^{\theta} \leq a \leq U(n) \leq b \leq bn^{\theta}$.
It is now easy to prove by induction on $k$ that $an^{\theta} \leq U(n) \leq bn^{\theta} \, \forall n \in [2^k, 2^{k+1}]$. When $k=0, 1, 2$, the statement is trivial. Suppose that it holds for $1 \leq k \leq i, i \geq 2$. Consider $n \in [2^{i+1}, 2^{i+2}]$, then  
\begin{align}
an^{\theta}& =a(\left(\frac{n}{2}\right)^{\theta}+\left(\frac{n}{4}\right)^{\theta}+\left(\frac{n}{8}\right)^{\theta}) \\
& \leq U(n) \\
& =U\left(\frac{n}{2}\right)+U\left(\frac{n}{4}\right)+U\left(\frac{n}{8}\right) \\
& \leq b(\left(\frac{n}{2}\right)^{\theta}+\left(\frac{n}{4}\right)^{\theta}+\left(\frac{n}{8}\right)^{\theta}) \\
&=bn^{\theta}
\end{align}
We are thus done by induction.
