Using Sigma Notation to Prove \sum_{k=M}^{N} 2^{-k} = 2(2^{-M} - 2^{-N})

[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?

 

[benorin]

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

 

[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})$$

 

[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)$$

 

[dekoi]

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

 

[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:

2ⁿ - 1
= 2ⁿ - 2⁰
= 2ⁿ + 0 + 0 + ... + 0 - 2⁰
= 2ⁿ + (-2^n-1 + 2^n-1) + (-2^n-2 + 2^n-2) + ... + (-2¹ + 2¹) - 2⁰
= (2ⁿ + 2^n-1 + ... + 2¹) - (2^n-1 + 2^n-2 + ... + 2⁰)
= 2(2^n-1 + 2^n-2 + ... + 2⁰) - (2^n-1 + 2^n-2 + ... + 2⁰)
= (2^n-1 + 2^n-2 + ... + 2⁰)

 

[dekoi]

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

 

[benorin]

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

 

[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.

 

[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}$$

 

[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.

 

[dekoi]

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}$$

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}$$

 

[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.

 

[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})$$

 

[benorin]

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})$$

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.

 

[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 got to go...

 

[dekoi]

I don't quite understand.

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