# Which is the “fastest” way to compute $\sum \limits_{i=1}^{10} \frac{10i-5}{2^{i+2}}$?

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,

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

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

-

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

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

-
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}} \,.$$

-

$\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.

-