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?