# Simplifying summations

1. Jan 22, 2007

### nightcrrawlerr

1. The problem statement, all variables and given/known data

Simplify the summation statement.

2. Relevant equations

a.) $$\sum^n _{k=0} = \frac{k-1}{2^k}$$

b.) $$\sum^{\infty} _{k=0} = (3k - 3^k)$$

c.) $$\sum^n _{k=1} = \frac{-1}{k(k + 1)}$$

3. The attempt at a solution

Kindly post here some link of the tutorial for Algorithm analysis.

thank you.

Last edited: Jan 23, 2007
2. Jan 30, 2007

### nightcrrawlerr

b.) $$\sum^{\infty} _{k=0} = (3k - 3^k)$$

$$= \sum^{\infty} _{k=0} 3k - \sum^{\infty} _{k=0} 3^k)$$

$$= 3(n(n+1)/2) - c3^n^+^1)$$

Last edited: Jan 30, 2007
3. Jan 30, 2007

### Dick

Note for b) the sum is infinite. This makes it easy. For a) and c) try to think of an easy power series in x that can give you terms like these if you put x=1. Remember you can get factors of k, k-1 etc by differentiating and 1/k,1/(k+1) by integrating your power series. Nuff hints?

4. Jan 30, 2007

### Staff: Mentor

What in the world are you folks talking about? Sorry if this a standard form that I'm not familiar with, but what is the object of the sum in each case? In my experience, the summation notation all by itself is meaningless. You need to do a sum of something over the limits. Do you mean this?

a.) $$\sum^n _{k=0} \frac{k-1}{2^k} = ?$$

5. Jan 30, 2007

### Dick

Clearly. The intent was so obvious I missed the misplaced = sign.

6. Jan 30, 2007

### Dick

Picky.............. I've been alerted that I need at least 10 characters in a response.

7. Jan 30, 2007

### Staff: Mentor

Okay, sorry about my flip response. I had problems back in my freshman college year when I didn't understand how important the format of an equation was, and being careful about equal signs helped me a lot to understand what an equation means.

EDIT -- I removed some insulting words from my post -- apologies to Dick.

Last edited: Feb 1, 2007
8. Jan 31, 2007

### Dick

Crabby retort expunged.

Last edited: Jan 31, 2007
9. Jan 31, 2007

### Staff: Mentor

You're right, that was not a good thing for me to say. I'll delete it out of my post. I guess it just struck a chord with me -- early in my college work, I had a fundamental lack of understanding of how equations worked, and that slowed my initial progress. I apologize for the chiding question.

Last edited: Jan 31, 2007
10. Jan 31, 2007

### Dick

And I apologize for taking offense where none was meant. I'll try and delete my crabby retort.

11. Jan 31, 2007

### Tom Mattson

Staff Emeritus
Yep, I agree.

I'm not so sure that will help. The summations aren't from 1 to infinity (as they are in a power series), they're from 1 to n.

For b), you could start by splitting it up into 2 sums:

$$\sum^n_{k=0}\frac{k-1}{2^k}=\sum^n_{k=1}\frac{k}{2^k}-\sum^n_{k=0}\frac{1}{2^k}$$

Note that the second sum on the RHS only needs to start at 1, not 0. As for the second sum, it's geometric, which makes the sum easy to find. I don't have any clues for you about the first one on the RHS. Try to work it out, and post what you come up with if you get stuck.

For c), I think the best way to tackle it would be to recognize that the summand is telescoping. You can see that by decomposing it into partial fractions, then writing out the first several terms. It should be easy to simplify it from there.

12. Jan 31, 2007

### Dick

A FINITE geometric series can be summed in closed form as well. And differentiated, and integrated. Consider a finite sum of terms like (x/2)^k. Differentiate it, set x=1 and compare with a). For c) consider integrating a similar finite sum.

13. Jan 31, 2007

### Tom Mattson

Staff Emeritus
I know that. In fact, I said it!

What I don't see is the connection between power series and finite sums. Could you please explain what you meant by "For a) and c) try to think of an easy power series in x that can give you terms like these if you put x=1"?

14. Jan 31, 2007

### nightcrrawlerr

To those who reply, thanks a lot!

Kindly post also some of the books or reference where I can fully understand this.

Again thanks a lot.

15. Jan 31, 2007

### nightcrrawlerr

for a. ) = $$\sum^n _{k=0} (3k - 3^k)$$

$$= 3 \sum^n _{k=0} k - \sum^n _{k=0} 3^k$$

$$= 3 (n(n + 1)/2) - 3n$$

$$= 3 - 3n$$

$$= n$$

for b.) $$\sum^{\infty} _{k=0} \frac{k-1}{2^k}$$

i have no answer yet... pls help.

for c.) $$\sum^n _{k=1} \frac{-1}{k(k + 1)}$$

$$= \sum^n _{k=1} (\frac{k-1} {k(k + 1)}) - (\frac {1}{(k + 1)})$$

$$= 1 - 1 / n$$

Last edited: Feb 1, 2007
16. Jan 31, 2007

### nightcrrawlerr

Thanks Guru, great help.

Still I couldn't figure it out. By the way what's RHS?

Could you recomend some reading, books, website links, and etc. to further my study of this, please.

Thanks.

Last edited: Jan 31, 2007
17. Feb 1, 2007

### Dick

$$\sum^n_{k=0}(\frac{x}{2})^k= \frac{1-(\frac{x}{2})^{n+1}}{1-(\frac{x}{2})}$$

Right? Assuming I did the tex ok. Differentiate, put x=1. The LHS is the tough part of a). The RHS is the answer.

Last edited: Feb 1, 2007
18. Feb 1, 2007

### Dick

I note in the reposted equations a) and b) have undergone a recombination.

19. Feb 1, 2007

### Tom Mattson

Staff Emeritus
Hehe, sorry.

RHS=Right Hand Side
LHS=Left Hand Side

The only part of this that wasn't answered as of my last post, has now been answered by Dick. Can you be specific about what is still giving you trouble?

I am drawing only on my knowledge of what we here in the States call "Calculus II".

20. Feb 1, 2007

### Tom Mattson

Staff Emeritus
OK, I understand you now. The part that confused me was when you said to use a "power series". What you have posted above is not a power series, because it doesn't have infinitely many terms.

Though I suppose you could turn it into a power series by letting the index run to infinity and multiplying the summand by a coefficient $a_k$ that is 1 for $0 \leq k \leq n$ and 0 for $n+1 \leq k \leq \infty$. Meh, whatever.