Let
gmax = max(g1, g2), and gmin = min(g1, g2).
gmin is O(gmax). Now, using the definition:
gmin(n) <= c*gmax(n) for n > some k
Adding gmax(n) to each side gives:
gmin(n) + gmax(n) <= c*gmax(n) + gmax(n) for n > some k
gmin(n) + gmax(n) <= (c+1)*gmax(n) for n > some k
g1(n) + g2(n) <= c'*gmax(n) for n > some k
So we have g1+g2 is O(max(g1, g2)).
Since f1+f2 is O(g1+g2), the transitive property of big-O gives us f1+f2 is O(max(g1, g2)). QED.