Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am looking for the "fastest" paper-pencil approach to compute $$\sum \limits_{i=1}^{10} \frac{10i-5}{2^{i+2}} $$

This is a quantitative aptitude problem and the correct/required answer is $3.75$

In addition, I am also interested to know how to derive a closed form for an arbitrary $n$ using mathematica I got $$\sum \limits_{i=1}^{n} \frac{10i-5}{2^{i+2}} = \frac{5 \times \left(3 \times 2^n-2 n-3\right)}{2^{n+2}}$$

Thanks,

share|improve this question
2  
Does someone feel like writing an "abstract duplicate" for this kind of question? I think I've seen several of them, but I don't know whether we have one that deals with this more generally and would serve as a good duplicate for all of them. –  joriki Nov 12 '11 at 15:55
1  
The actual correct answer to this question is $\approx 3.7219$. I do not know what "quantitative aptitude test" means, but would not 3.7 be a better answer than 3.75? –  Aleksey Pichugin Nov 12 '11 at 16:36

5 Answers 5

up vote 3 down vote accepted

An approximate answer

We'll split the sum you're looking for up into

$$ 10 \sum_{i=1}^{10} {i \over 2^{i+2}} - 5 \sum_{i=1}^{10} {1 \over 2^{i+2}}. $$

Call this $10S_1 - 5S_2$.

We can write $$ S_1 = \sum_{i=1}^{10} {i \over 2^{i+2}} = {1 \over 4} \sum_{i=1}^{10} {i \over 2^i} $$ and the result $\sum_{i=1}^\infty i/2^i = 2$ is well-known; thus $S_1 \approx 1/2$.

Similarly, $S_2 \approx \sum_{i=1}^\infty 1/2^{i+2} = 1/4$ by the usual sum of a geometric series.

So your sum is approximately $15/4$. In fact the infinite sum

$$ \sum_{i=1}^\infty {10i-5 \over 2^{i+2}} $$

is exactly 15/4. We've left off some small positive terms so your sum is a bit less than $15/4$.

An exact form for the sum

As for getting an exact form for the sum: call it $f(n)$. Then we have

$$ f(n) = {15 \over 4} - \left( 10 \sum_{i=n+1}^\infty {i \over 2^{i+2}} - 5 \sum_{i=n+1}^\infty {1 \over 2^{i+2}} \right). $$

Write this as $f(n) = 15/4 - g(n) + h(n)$.

$h(n)$ is easy -- it's the sum of a geometric series with its first term $5/2^{n+3}$ and ratio $1/2$, so $h(n) = 5/2^{n+2}$.

$g(n)$ is a bit harder. So that we don't have so many constants floating around, consider

$$ G(n) = \sum_{i={n+1}}^\infty {i \over 2^i} $$

and you can see $g(n) = (5/2) G(n)$. Now you can write

$$ G(n) = {(n+1) \over 2^{n+1}} + {{n+2} \over 2^{n+2}} + {{n+3} \over 2^{n+3}} + \cdots $$

and this is just

$$ G(n) = \left( {n \over 2^{n+1}} + {n \over 2^{n+2}} + {n \over 2^{n+3}} + \cdots \right) + {1 \over 2^n} \left( {1 \over 2^1} + {2 \over 2^2} + {3 \over 2^3} + \cdots \right). $$

The first sum is a geometric series, summing to $n/2^n$; the second sum is $2$. Thus $G(n) = (n+1)/2^n$. Therefore you get

$$ f(n) = {15 \over 4} - {5 \over 2} {(n+2) \over 2^n} + {5 \over 2^{n+2}}. $$

A sum that everybody should know, but lots of people don't

Finally, I used the result $\sum_{i=1}^\infty i/2^i$ twice here, both in getting the approximation and in getting the exact form. How can we prove that? One way is to write $$ {1 \over 2} + {2 \over 4} + {3 \over 8} + {4 \over 16} + \cdots $$ as a sum of one $1/2$, two $1/4$s, three $1/8$s, and so on; then regroup those terms as $$ \left( {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) + \left( {1 \over 4} + {1 \over 8} + {1 \over 16} + \cdots \right) + \left( {1 \over 8} + {1 \over 16} + {1 \over 32} + \cdots \right) + \cdots $$ Each pair of parentheses contains a geometric series; summing those gives $1 + 1/2 + 1/4 + 1/8 + \cdots$, another geometric series, which has sum $2$.

Alternatively, note that $$ {1 \over 1-z} = 1 + z + z^2 + z^3 + \cdots $$ and differentiating both sides gives $$ {1 \over (1-z)^2} = 1 + 2z + 3z^2 + \cdots $$. Multiply both sides by $z$ to get $$ {z \over (1-z)^2} = z + 2z^2 + 3z^3 + \cdots $$ and plug in $z = 1/2$ to get $$ {1/2 \over (1-1/2)^2} = {1 \over 2} + {2 \over 2^2} + {3 \over 2^3} + \cdots. $$

share|improve this answer

I would do it like this. Using $x \frac{\mathrm{d}}{\mathrm{d} x}\left( x^k \right) = k x^k$, and $\sum_{k=1}^n x^k = x \frac{x^n-1}{x-1}$. Then $$\begin{eqnarray} \sum_{k=1}^n \left( a k +b\right) x^k &=& \left( a x \frac{\mathrm{d}}{\mathrm{d} x} + b\right) \circ \sum_{k=1}^n x^k = \left( a x \frac{\mathrm{d}}{\mathrm{d} x} + b\right) \circ \left( x \frac{x^n-1}{x-1} \right) \\ &=& x \left( a x \frac{\mathrm{d}}{\mathrm{d} x} + a + b\right) \circ \left(\frac{x^n-1}{x-1} \right) \\ &=& x \left( (a+b) \frac{x^n-1}{x-1} + a x \frac{ n x^{n-1}(x-1) - (x^n-1) }{(x-1)^2} \right) \\ &=& x \left( (a+b) \frac{x^n-1}{x-1} + a x \frac{ (n-1) x^{n} - n x^{n-1} + 1 }{(x-1)^2} \right) \end{eqnarray} $$

Now applying this: $$ \begin{eqnarray} \sum_{k=1}^n \frac{10 k -5}{2^{k+2}} &=& \frac{5}{4} \sum_{k=1}^n (2k-1)\left(\frac{1}{2}\right)^k \\ &=& \frac{5}{4} \frac{1}{2} \left( -(2^{1-n} - 2) + (n-1) 2^{2-n}- n 2^{1-n} + 4 \right) \\ &=& \frac{5}{4} \left( 3 + (n-3) 2^{-n} \right) \end{eqnarray} $$

share|improve this answer
    
Thanks for doing this in general form. If you don't mind I'll use this question for duplicates in the future and point to this answer :-) –  joriki Nov 13 '11 at 8:04
    
@joriki:Question is tagged as algebra-precalculus. –  Quixotic Nov 18 '11 at 7:31
    
@MaX: I see. Thanks for pointing that out. Fortunately there are so many answers here, including N.S.' that shows an elementary way to sum $i/q^i$, that it will still be a good duplicate in many future circumstances. I wonder which answer you'll be accepting... –  joriki Nov 18 '11 at 7:39
    
@joriki:You are welcome, I am accepting Michael Lugo's answer as it provides the fastest method to reach the solution. –  Quixotic Nov 19 '11 at 14:17
    
You presented this beautifully. Thank you. –  000 Jul 14 '12 at 9:48

First note that $\displaystyle\frac{10i-5}{2^{i+2}} = \frac{5(2i-1)}{2^{i+2}}$

Secondly, using the sum of a geometric series you can show that $2^0 + 2^1 + 2^2 + ... + 2^k = 2^{k+1}-1$.

$\displaystyle \begin{align*} \text{So } \sum \limits_{i=1}^{n} \frac{10i-5}{2^{i+2}} &= 5(\frac{2\times1-1}{2^{1+2}}+\frac{2\times2-1}{2^{2+2}}+\frac{2\times3-1}{2^{3+2}}+...+\frac{2\times n-1}{2^{n+2}})\\ &= 5(\frac{2^{n-1}(2\times1-1)+2^{n-2}(2\times2-1)+2^{n-3}(2\times3-1)+...+2^{0}(2\times n-1)}{2^{n+2}}) \\ &= 5(\frac{2(2^{n-1}\times1+2^{n-2}\times2+2^{n-3}\times3+...+2^{0}\times n)-(2^{n-1}+2^{n-2}+2^{n-3}+...+1)}{2^{n+2}})\\ &= 5(\frac{2(2^{n-1}\times1+2^{n-2}\times2+2^{n-3}\times3+...+2^{0}\times n)-(2^n-1)}{2^{n+2}})\\ &= 5(\frac{2((2^{n-1}+2^{n-2}+2^{n-3}+...+1)+(2^{n-2}+2^{n-3}+2^{n-4}+...+1)+...+(2+1)+(1))-(2^n-1)}{2^{n+2}})\\ &= 5(\frac{2((2^{n}-1)+(2^{n-1}-1)+(2^{n-2}-1)+...+(2^{2}-1)+(2-1))-(2^n-1)}{2^{n+2}})\\ &= 5(\frac{2((2^{n}+2^{n-1}+2^{n-2}+...+2) + (-1)\times n)-(2^n-1)}{2^{n+2}})\\ &= 5(\frac{2(2\times (2^n - 1))- n)-(2^n-1)}{2^{n+2}})\\ &= 5(\frac{4 \times 2^n - 4 - 2n -2^n + 1}{2^{n+2}})\\ &= 5(\frac{3 \times 2^n - 2n - 3}{2^{n+2}})\text{ which is the closed form you got from Mathematica}\end{align*}$

share|improve this answer
    
The equations are a lot more readable in display style, which you get either by switching it on individually with \displaystyle or by making the entire formula a displayed one by enclosing it in double dollar signs. Also note that you can use the eqnarray and align environments to align consecutive equations with each other. –  joriki Nov 13 '11 at 8:03
    
@joriki Thanks for the tips and I think my answer has been formatted correctly but I believe my 5th line is a tad too long? I had to trim is down a bit and it is still quite long... –  Sp3000 Nov 13 '11 at 9:50
    
Yes, that's a problem actually, which I didn't foresee when I wrote my comment :-) You can alleviate it somewhat by not putting the "So" into the equation but on a line of its own. Also, though it looks nicer with a full equation in the first line, in this case you could break the line before the first equals sign; it will still look better with eqnarray since you can align the expression in the first line with the other expressions instead of with the equals signs. –  joriki Nov 13 '11 at 10:03

The sum $S= \sum \limits_{i=1}^n \frac{1}{2^i}=1-\frac{1}{2^n}$ is geometric, thus easy to calculate.

Here is a simple elementary way of calculating

$$T=\sum_{i=1}^n \frac{i}{2^i} \,.$$:

$$T=\sum_{i=1}^n \frac{i}{2^i} =\frac{1}{2}+ \sum_{i=2}^n \frac{i}{2^i} =\frac{1}{2}-\frac{n+1}{2^{n+1}}+ \sum_{i=2}^{n+1} \frac{i}{2^i} \,.$$

Changing the index in the last sum yields:

$$T= \frac{2^n-n-1}{2^{n+1}}+\sum_{i=1}^{n} \frac{i+1}{2^{i+1}}=\frac{2^n-n-1}{2^{n+1}}+\sum_{i=1}^{n} \frac{i}{2^{i+1}}+\sum_{i=1}^{n} \frac{1}{2^{i+1}} \,.$$

Thus

$$T= \frac{2^n-n-1}{2^{n+1}}+\frac{1}{2}T+ \frac{1}{2}-\frac{1}{2^{n+1}}$$

Thus

$$\frac{1}{2}T=\frac{2^{n+1}-n-2}{2^{n+1}}\,.$$

Hence

$$\sum_{i=1}^n \frac{i}{2^i} =\frac{2^{n+1}-n-2}{2^{n}} \,.$$

share|improve this answer

$\sum \limits_{i=1}^{10} \frac{10i-5}{2^{i+2}} =\frac{10}{4} \sum_{i=1}^{10} \frac{i}{2^i}-\frac{5}{4}\sum_{i=1}^{10} \frac{1}{2^i}$

Second $\sum$ is obviously $1-\frac{1}{1024}$.

First $\sum$:

$\frac{1}{2} +$

$\frac{1}{4} + \frac{1}{4} +$

$\frac{1}{8} + \frac{1}{8} + \frac{1}{8} +$

$\vdots$

$\frac{1}{1024} + \frac{1}{1024} + \dots + \frac{1}{1024}$

Summing by columns, $(1-\frac{1}{1024})+(\frac{1}{2}-\frac{1}{1024})+\dots+(\frac{1}{512}-\frac{1}{1024})=(1+\frac{1}{2}+\dots+\frac{1}{512})-\frac{10}{1024}=\frac{1023}{512}-\frac{10}{1024}$

Rest is boring and easy.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.