title: Recurrence relation: iteration solving
body: <p>There is a recurrence relation as following:</p>
  
  <pre><code>T(n) = 2 T(n-1) + O(1) for n &gt; 1 
  otherwise, its T(n) = O(1)
  </code></pre>
  
  <p>By iteration , so far I got like,</p>
  
  <pre><code>T(n) = 2(2T(n-2) + 1) + 1 --- 1
  T(n) = 2(2(2T(n-3) + 1) + 1) + 1 ---- 2
  T(n) = 2(2(2(2T(n-4) + 1) + 1) + 1) + 1 ------3
  T(n) = 2(2(2(2(2T(n-5) + 1) + 1) + 1) + 1) +1 ----- 4
  </code></pre>
  
  <p>I am not sure what to do next to find the upper bound time complexity. Could anyone please help me with this.</p>