title: Recurrence relation: T(n) = T(n - 1) + n - 1
body: <p>I am trying to understand how to solve recurrence relations. I understand it to the point where we have to simplify.</p>
  
  <pre><code>T(N) = T(N-1) + N-1              Initial condition: T(1)=O(1)=1
  T(N) = T(N-1) + N-1
  T(N-1) = T(N-2) + N-2
  T(N-2) = T(N-3) + N-3
  ……
  T(2) = T(1) + 1
  
  
  **Summing up right and left sides**
  
  T(N) + T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) =
  
  = T(N-1) + T(N-2) + T(N-3) + …. T(3) + T(2) + T(1) +
  
  (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1
  
  
  ** Canceling like terms and simplifying **
  
  T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2
  
  T(N) = 1 + N*(N - 1)/2
  </code></pre>
  
  <p>I really don't understand the last part. I understand canceling like terms but don't understand how the simplification below works:</p>
  
  <pre><code>T(N) = T(1) + (N-1) + (N-2) + (N-3) + …. +3 + 2 + 1
  T(N) = T(1) + N*(N-1)/2 1 + N*(N - 1)/2
  </code></pre>
  
  <p>How is the second line derived from the first? Doesn't make any sense to me.</p>
  
  <p>Would be a great help if someone can help me understand this. Thanks =)</p>