1
$\begingroup$

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,

  • 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?2011-11-12

5 Answers 5

3

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

3

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

  • 0
    You presented this beautifully. Thank you.2012-07-14
2

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

  • 0
    Yes, that's a problem actually, which I did$n$'t foresee whe$n$ 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.2011-11-13
1

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

1

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