# Sigma Notation

1. Nov 11, 2005

### dekoi

Show that:
$$\sum_{k=0}^{N} a_k = \sum_{k=M}^{M+N} a_{k-M}$$

I did this, my answer is:
$$\sum_{k=0}^{N} a_k = a_0 + a_1 + a_2 + ... + a_N$$

$$\sum_{k=M}^{M+N} a_{k-M} = a_{M-M} + a_{M+1-M} + a_{M+2-M} + ... + a_{M+N-M} = a_0 + a_1 + a_2 + ... + a_N$$

Now, I have to use this to prove that:
$$\sum_{k=M}^{N} 2^{-k} = 2(2^{-M} - 2^{-N})$$

So, I tried expanding the sum:
$$\sum_{k=M}^{N} 2^{-k} = 2^{-M} + 2^{-(M+1)} + 2^{-(M+2)} + ... + 2^{-N}$$

I factored out some 2's:
$$\sum_{k=M}^{N} 2^{-k} = 2^{-M}2^{0} + 2^{-M}2^{-1} + 2^{-M}2^{-2} + ... + 2^{-M}2^{-N} = 2^{-M}(2^{0} + 2^{-1} + 2^{-2} + ... + 2^{-N})$$

Which I'm assuming is equal to some other sum:
$$\sum_{k=M}^{N} 2^{-k} = 2^{-M}(\sum_{i=0}^{N} 2^{-i})$$

However, I don't know how to continue this. Any suggestions?

2. Nov 11, 2005

### benorin

Hint: $$\sum_{k=M}^{N} 2^{-k} = \sum_{k=0}^{N} 2^{-k}-\sum_{i=0}^{M-1} 2^{-i}$$

3. Nov 11, 2005

### dekoi

That doesn't seem to work.
I get:
$$\sum_{k=M}^{N} 2^{-k} = \sum_{k=0}^{N} 2^{-k}-\sum_{i=0}^{M-1} 2^{-i}$$
$$\sum_{k=M}^{N} 2^{-k} = (2^{0} + 2^{-1} + 2^{-2} + ... + 2^{-N}) - (2^{0} + 2^{-1} + 2^{-2} + ... + 2^{-M + 1}$$
$$= 2^{-N} - 2^{-M+1} = 2^{-N} + 2^{-M}2^{1}$$

Which will not equal to : $$2(2^{-M} - 2^{-N})$$

Last edited by a moderator: Nov 11, 2005
4. Nov 11, 2005

### benorin

$$a_{M}+a_{M+1}+\cdot\cdot\cdot+a_{N-1}+a_{N}=\left( a_{M}+a_{M+1}+\cdot\cdot\cdot+a_{N-1}+a_{N}\right) + \left[ \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{M-1}\right) - \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{M-1}\right) \right]$$
$$\left[ \left( a_{M}+a_{M+1}+\cdot\cdot\cdot+a_{N-1}+a_{N}\right) + \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{M-1}\right) \right] - \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{M-1}\right) = \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{N-1}+a_{N}\right) - \left( a_{0}+a_{1}+\cdot\cdot\cdot+a_{M-1}\right)$$

Last edited: Nov 11, 2005
5. Nov 11, 2005

### dekoi

Wait, we posted at the same time.
Read my previous post, I edited it.

6. Nov 11, 2005

### AKG

I think you mean:

$$\sum _{k=M} ^N = 2(2^{-M}\mathbf{)} - 2^{-N}$$

Anyways, I don't know how you'd prove this using what you proved first, but you can prove this if you know that:

2n - 1
= 2n - 20
= 2n + 0 + 0 + ... + 0 - 20
= 2n + (-2n-1 + 2n-1) + (-2n-2 + 2n-2) + ... + (-21 + 21) - 20
= (2n + 2n-1 + ... + 21) - (2n-1 + 2n-2 + ... + 20)
= 2(2n-1 + 2n-2 + ... + 20) - (2n-1 + 2n-2 + ... + 20)
= (2n-1 + 2n-2 + ... + 20)

7. Nov 11, 2005

### dekoi

No, no... I wrote the sum correctly.

8. Nov 11, 2005

### benorin

AKG is right: $$\sum _{k=M} ^N 2^{-k}= 2(2^{-M}\mathbf{)} - 2^{-N}$$

9. Nov 11, 2005

### AKG

Well it's false so good luck proving it:

M = 3, N = 4

$$\sum_{k=M}^{N} 2^{-k} = 2(2^{-M} - 2^{-N})$$

$$\sum_{k=3}^{4} 2^{-k} = 2(2^{-3} - 2^{-4})$$

$$2^{-3} + 2^{-4} = 2(2^{-3} - 2^{-4})$$

$$\frac{1}{8} + \frac{1}{16} = 2(\frac{1}{8} - \frac{1}{16})$$

$$\frac{3}{16} = 2(\frac{1}{16})$$

$$3 = 2$$

Good luck.

10. Nov 11, 2005

### benorin

Here's one way to do it:

$$\sum_{k=M}^{N} 2^{-k} = \sum_{k=0}^{N} 2^{-k}-\sum_{i=0}^{M-1} 2^{-i}$$

the later sums are geometric... recall that the partial sum thereof is

$$1+r+r^2+r^3+\cdot\cdot\cdot+r^n=\frac{1-r^{n+1}}{1-r}$$

11. Nov 11, 2005

### dekoi

This is going to be tricky... especially since the question I'm given has an error in it itself :S.
I guess I will have to try your methods.

Thank you AKG and benorin.

I'll get back to you if I have any problems.

12. Nov 11, 2005

### dekoi

Well, that is the partial sum for a positive n, but in my case-- there is a negative n.
What is the partial sum for :
$$\sum_{i=0}^{N} 2^{-i}$$

13. Nov 11, 2005

### benorin

$$2^{-i}=\left( 2^{-1}\right)^{i}=\left( \frac{1}{2}\right)^{i}$$

hence $$\sum_{i=0}^{N} 2^{-i}= \sum_{i=0}^{N}\left( \frac{1}{2}\right)^{i} = \frac{1-\left( \frac{1}{2}\right)^{N+1}}{1-\frac{1}{2}}=2\left( 1-2^{-(N+1)}\right)$$

do likewise for $$\sum_{i=0}^{M-1} 2^{-i}$$ and subtract.

14. Nov 11, 2005

### dekoi

Why am I doing likewise for $$\sum_{i=0}^{M-1} 2^{-i}$$ ?

This was my last step: $$\sum_{k=M}^{N} 2^{-k} = 2^{-M}(\sum_{i=0}^{N} 2^{-i})$$

15. Nov 11, 2005

### benorin

the last term of the sum on left is $$2^{-N}$$ on the right the last term is $$2^{-(N+M)}$$, so their not equal.

16. Nov 11, 2005

### benorin

$$2^{-i}=\left( 2^{-1}\right)^{i}=\left( \frac{1}{2}\right)^{i}$$

hence $$\sum_{i=0}^{N} 2^{-i}= \sum_{i=0}^{N}\left( \frac{1}{2}\right)^{i} = \frac{1-\left( \frac{1}{2}\right)^{N+1}}{1-\frac{1}{2}}=2\left( 1-2^{-(N+1)}\right)$$

do likewise for $$\sum_{i=0}^{M-1} 2^{-i}$$, that is

$$\sum_{i=0}^{M-1} 2^{-i}= \sum_{i=0}^{M-1}\left( \frac{1}{2}\right)^{i} = \frac{1-\left( \frac{1}{2}\right)^{(M-1)+1}}{1-\frac{1}{2}}=2\left( 1-2^{-M}\right)$$

and subtract:

$$\sum_{k=M}^{N} 2^{-k} = \sum_{k=0}^{N} 2^{-k}-\sum_{i=0}^{M-1} 2^{-i}= 2\left( 1-2^{-(N+1)}\right) - 2\left( 1-2^{-M}\right) = 2^{1-M}-2^{-N}$$

Sorry to be short, but gotta go...

17. Nov 11, 2005

### dekoi

I don't quite understand.

I realize that your method is correct, but I don't understand why.