How to find a function that is the upper bound of this sum? The Problem
Consider the recurrence 
$ T(n) =
\begin{cases}
c  & \text{if $n$ is 1} \\
T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1}
\end{cases}$
A. Express the cost of all levels of the recursion tree as a sum over the cost of each level of the recursion tree
B. Give a function $g(n)$ and show that it is an upper bound on the sum 
My Work
I was able to do part A. I drew the first six levels of the recursion tree and expressed the expressed the cost of all levels as $\sum_{i=0}^{log_2n} \frac{4n}{2^i}f(i+2) $ where $f(n)$ is the $n$th term in the Fibonacci sequence(0, 1, 1, 2, 3, 5, 8)
How would I come up with a function that would be an upper bound of this sum? 
 A: Suppose we start by solving the following recurrence:
$$T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + 4n$$
where $T(1) = c$ and $T(0) = 0.$
Now let $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
be the binary representation of $n.$
We unroll the recursion to obtain an exact formula for $n\ge 2$
$$T(n) = c [z^{\lfloor \log_2 n \rfloor}] \frac{1}{1-z-z^2}
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
[z^j] \frac{1}{1-z-z^2} 
\sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
We recognize the generating function  of the Fibonacci numbers, so the
formula becomes
$$T(n) = c F_{\lfloor \log_2 n \rfloor +1}
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^{k-j}.$$
We now compute lower and  upper bounds which are actually attained and
cannot  be improved upon.  For the  lower bound  consider a  one digit
followed by a string of zeroes, to give
$$T(n) \ge c F_{\lfloor \log_2 n \rfloor +1}
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} 2^{\lfloor \log_2 n \rfloor-j}
\\ = c F_{\lfloor \log_2 n \rfloor +1}
+ 8 \times 2^{\lfloor \log_2 n \rfloor}
\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} 2^{-j-1}.$$
Now since $$|\varphi|=\left|\frac{1+\sqrt{5}}{2}\right|<2$$
the sum term converges to a number, we have
$$\frac{1}{2} \le 
\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} F_{j+1} 2^{-j-1}
\lt \sum_{j=0}^{\infty} F_{j+1} 2^{-j-1}
= 2.$$
For an upper bound consider a string of one digits to get
$$T(n) \le c F_{\lfloor \log_2 n \rfloor +1}
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^{k-j}
\\ = c F_{\lfloor \log_2 n \rfloor +1}
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} (2^{\lfloor \log_2 n \rfloor+1-j} - 1)
\\ = c F_{\lfloor \log_2 n \rfloor +1}
- 4 (F_{\lfloor \log_2 n \rfloor +2} -1)
+ 4 \sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} 2^{\lfloor \log_2 n \rfloor+1-j}
\\ = c F_{\lfloor \log_2 n \rfloor +1}
- 4 (F_{\lfloor \log_2 n \rfloor +2} -1)
+ 4  \times 2^{\lfloor \log_2 n \rfloor+1}  
\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} 2^{-j}
\\ = c F_{\lfloor \log_2 n \rfloor +1}
- 4 (F_{\lfloor \log_2 n \rfloor +2} -1)
+ 16 \times 2^{\lfloor \log_2 n \rfloor}  
\sum_{j=0}^{\lfloor \log_2 n \rfloor-1} 
F_{j+1} 2^{-j-1}.$$
The same  constant appears as in  the lower bound. Now  since the term
$F_{\lfloor  \log_2   n  \rfloor}$  is   asymptotically  dominated  by
$2^{\lfloor  \log_2   n  \rfloor}$  (we  have   $F_{\lfloor  \log_2  n
\rfloor}\in o(2^{\lfloor \log_2  n \rfloor})$ because $F_{\lfloor  \log_2  n
\rfloor} \in\Theta(\varphi^{\lfloor  \log_2   n  \rfloor}))$ joining the
upper  and  the  lower  bound  we  get for  the  asymptotics  of  this
recurrence that it is
$$T(n)\in\Theta\left(2^{\lfloor \log_2  n \rfloor}\right)
= \Theta\left(2^{\ \log_2  n}\right) = \Theta(n),$$
which, let it be said, could also have been obtained by inspection.

Remark. The evaluation of the constant is done by noting that
the generating function of
$$F_{j+1} 2^{-j-1}\quad
\text{is}\quad\frac{1/2}{1-z/2-z^2/4}$$
which at $z=1$ evaluates to $\frac{1/2}{1-1/2-1/4} = 2.$
We have a certain flexibility as to what power of two to use in the constant but this does not affect the asymptotics.

This MSE link has a similar calculation.
A: In light of the detailed solution of @Marko Riedel, if you only want to show that $T(n)=O(n)$, you can make the (somewhat easier computation):
Base case: (ok)
Inductive Hypothesis: $T(k)\leq Ck$ for $k<n$ for some constant $c>0$.
Then, prove the inductive step:
\begin{align*}
T(n) &= T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4))+4n \\
     &\leq T(n/2)+T(n/4) + 4n & \text{by monotonicity} \\
     &\leq C(n/2)+C(n/4) + 4n \\
     &=(3C/4+4)n \\
     &=Cn & \star\star
\end{align*}
Where $\star\star$ is true if $(3C/4+4)=C$ which works when $C=16$.
So, the moral of the story is that if you can guess that $T(n)=O(n)$ it is not hard to prove it by induction.
EDIT: One final note, it wasn't asked to get a $\Theta$ bound on $T(n)$, but it is pretty clear (by the recurrence) that $T(n)=\Omega(n)$ since $T(n)\geq 4n$.  Then, combining this with the previous argument shows that $T(n)=\Theta(n)$.
