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? 

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)$.
