title: Using recurrence relations to prove a function has exponential runtime?
body: <p>Here is a simple C program:</p>
  
  <pre><code>int f(int n) {
    if(n==0 || n==1) {
      return n;
    } else {
      return 2 * f(n - 1) + 3 * f(n - 2);
    }
  } 
  </code></pre>
  
  <p>This program has exponential time complexity.  You can see this in this diagram of the function calls for <code>f(5)</code>:</p>
  
  <p><img src="https://i.stack.imgur.com/OjIXt.jpg" alt="n  = 5"></p>
  
  <p>I want to show that the function has exponential complexity using a recurrence equation only, not by drawing a diagram and counting the number of function calls.</p>
  
  <p>The recurrence relation I came up with is</p>
  
  <blockquote>
    <p>T(n) = T(n-1) + T(n-2) + c</p>
  </blockquote>
  
  <p>Expanding gives</p>
  
  <blockquote>
    <p>T(n) = 2T(n - 2) + T(n - 3) + 2c</p>
  </blockquote>
  
  <p>However, I don't know how to solve this further.  How can I solve this recurrence relation?</p>