searching for a formula for $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$ So we have a number $n$, which is a power of two.
And we have the following recursion:
 $$ T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$$
I solved some exercises like this, but I have a problem with this one.
I don't see the structure:
for the first recursion I have obviously have 
$ T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$
for second recursion :
$ T(n) = 2T(\frac{n}{4}) + T(\frac{n}{8}) +  \frac{n}{2} +n$
for third recursion :
$ T(n) = 3T(\frac{n}{8}) + 2T(\frac{n}{16}) +  2\frac{n}{4}+ \frac{n}{2}  +n$
for the fourth recursion :
$ T(n) = 5T(\frac{n}{16}) + 3T(\frac{n}{32}) +  3\frac{n}{8}+ 2\frac{n}{4} +\frac{n}{2}  +n$
for the fifth recursion :
$ T(n) = 8T(\frac{n}{32}) + 5T(\frac{n}{64}) +  5\frac{n}{16}+ 3\frac{n}{8} +2\frac{n}{4} + \frac{n}{2}  +n$
.
. 
. 
So we see that for $k$ we have :  
$T(n) =  ?T(\frac{n}{2^k})+ ?T(\frac{n}{2^{k+1}}) + \sum_{i=0}^{k-1} ? \frac{n}{2^i}$
As you can see the prefactors are missing.

For $n=2^N$ let $F(N)=T(n)$. Then
$$T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + n$$
implies that
$$F(N) = F(N-1) + F(N-2) + 2^N.$$
which is a linear recurrence with characteristic equation $z^2-z-1=0$, the same of the Fibonacci sequence $1,1,2,3,5,8,13,\dots$. Hence the solution is
$$F(N)=A\varphi^N+B(-\varphi)^{-N}+2^{N+2}$$
where $1<\varphi=\frac{1+\sqrt{5}}{2}<2$, and $A,B$ are constants which depend on the initial terms $F(0)=T(1)$ and $F(1)=T(2)$.
Can you take it from here?
