I'm currently taking a class on computer algorithms where we are trying to determine efficiency classes. I realized in this process that I am unclear on how to compute certain summations and was wondering if someone could point me in the right direction.

 

We have been given the following example:

 

[latex]\sum\limits_{i=0}^{n-2} \sum\limits_{j=i+1}^{n-1} 1 = \frac{n(n-1)}{2}[/latex]

 

I am not clear on how the RHS can be obtained from the LHS algebraically? I'm also a little uncertain on how to approach the following when asked to compute the summation:

 

[latex]\sum\limits_{j=1}^n 3^{j +1} [/latex]

 

I know this may be an easy question for some of you to answer. I've had some difficulty finding resources online which show how to solve summations algebraically.

 

Thanks in advance for any help.

For the first one, you need to count how many terms in the inner sum ((n-1) - (i+1) + 1). The outer sum is then an arithmetic series.

 

 

The second problem is a geometric series.

 

 

 

I suggest you look up both types of series on Wikipedia - this will give a thorough understanding.

This is helpful thank you. I will check out those articles to better understand these topics.

 

If anyone knows of some books that cover in depth the material mentioned above I'd be interested to check them out.

 

Cheers,

Max

This is helpful thank you. I will check out those articles to better understand these topics.

 

If anyone knows of some books that cover in depth the material mentioned above I'd be interested to check them out.

 

Cheers,

Max

 

I think you are overcomplicating the material in your mind. The concepts are quite simple. I believe I was first exposed to the material in 7th or 8th grade and both (arithmetic and geometric) progressions were covered in one class.