title: Complexity of the recursion: T(n) = T(n-1) + T(n-2) + C
body: <p>I want to understand how to arrive at the complexity of the below recurrence relation.</p>
  
  <p><code>T(n) = T(n-1) + T(n-2) + C</code>
  Given <code>T(1) = C</code> and <code>T(2) = 2C;</code></p>
  
  <p>Generally for equations like <code>T(n) = 2T(n/2) + C</code> (Given T(1) = C), I use the following method.</p>
  
  <pre><code>T(n) = 2T(n/2) + C
  =&gt; T(n) = 4T(n/4) + 3C
  =&gt; T(n) = 8T(n/8) + 7C
  =&gt; ...
  =&gt; T(n) = 2^k T (n/2^k) + (2^k - 1) c
  </code></pre>
  
  <p>Now when <code>n/2^k = 1 =&gt; K = log (n)</code> (to the base 2)</p>
  
  <pre><code>T(n) = n T(1) + (n-1)C
       = (2n -1) C
       = O(n)
  </code></pre>
  
  <p>But, I'm not able to come up with similar approach for the problem I have in question. Please correct me if my approach is incorrect.</p>