title: Proving Big-O Sum Rule?
body: <p>I am unsure how to formally prove the Big O Rule of Sums, i.e.:</p>
  
  <pre><code>f1(n) + f2(n) is O(max(g1(n)),g2(n))
  </code></pre>
  
  <p>So far, I have supposed the following in my effort:</p>
  
  <p>Let there be two constants <code>c1</code> and <code>c2</code> such that <code>c2 &gt; c1</code>. By Big O definition:</p>
  
  <pre><code>f1(n) &lt;= c1g1(n) and f2(n) &lt;= c2g2(n)
  </code></pre>
  
  <p>How should I proceed? Is it reasonable to introduce numerical substitutions for the variables at this step to prove the relationship? Not knowing <code>g</code> or <code>f</code>, that is the only way I can think to approach.</p>