Solving Summation Expressions

Question

I would like to know how do you solve summation expressions in an easy way (from my understanding). I am computer science student analyzing for loops and finding it's time complexity.

e.g

Code:

 for i=1 to n
      x++
 end for

Summation:

  n  
  ∑ 1
 i=1

Solving:

 = ∑ [n-1+1]     (topLimit - bottomLimit + 1)
 = n             (summation formula said ∑ 1 = 1+1+1+1+ ... + 1 = n)

The time complexity of the for loop is: O(n)

---

Code

for(i=0; i<=n i++)
    for(j=i; j<=n; j++)
        x++;

Question:

How do you solve:

   n    n
   ∑   [∑ 1]
  i=1  j=i

My Solution:

   n
=  ∑  [n-i+1]
  i=1
= not sure how to progress from here (should i do another topLimit - bottomLimit + [n-i+1]?)

The problem i am having is simplifying so i can get to say i, 1/i, i^2, .. i.e something i can use a summation formula on. I know the answer supposed to be: (n(n+1))/2.

Answer 1

You correctly got down to this sum: $$ \sum_{i=1}^n (n-i+1) $$ Now use the fact that finite sums are just additions, so you can use all the algebra rules you're used to and write it as $$ \begin{align} \sum_{i=1}^n ((n+1)-i) &= \sum_{i=1}^n(n+1)-\sum_{i=1}^n i\\ &=(n+1)\sum_{i=1}^n 1-\sum_{i=1}^n i \end{align} $$ Can you take it from there?

Answer 2

Breaking up the sum into separate summations:

$$ \sum_{i=1}^n(n+1-i) = \sum_{i=1}^nn + \sum_{i=1}^n1 - \sum_{i=1}^ni $$

Note the various summations rules, tricks, and simplifications for each of the summations.