0
$\begingroup$

To prove (1)

$$\sum_{i=1}^n \dfrac {i}{2^i} <2$$

Someone shows that (2)

$$\sum_{i=1}^n \dfrac {i}{2^i} = 2-\dfrac{n+2}{2^n}$$

so we can prove (1).

Can anyone guide me how from (1) they come up with (2) please ? On what base they find (2) ?

$\endgroup$
  • 1
    $\begingroup$ What is $2_i$ ??? If it was meant $2^ i$, then search MSE, e.g., here. $\endgroup$ – Dietrich Burde Aug 14 '17 at 15:29
  • $\begingroup$ I assume your $2_i$ should be $2^i$. Work out the value of (2) for $n = 1, 2, 3, 4, 5$ and guess the pattern. $\endgroup$ – Ethan Bolker Aug 14 '17 at 15:30
  • $\begingroup$ @ Dietrich Burde it's 2^i $\endgroup$ – xuoimai Aug 14 '17 at 15:31
  • $\begingroup$ To answer the first question, finding the closed form solution for the LHS would be one of the simplest approaches to the problem if it's possible. $\endgroup$ – Shuri2060 Aug 14 '17 at 16:14
1
$\begingroup$

$$S:=\sum_{i=1}^n\frac{i}{2^i}=\sum_{i=1}^n\frac{i-1}{2^i}+\sum_{i=1}^n\frac1{2^i}=\frac12\sum_{i=1}^n\frac{i-1}{2^{i-1}}+\frac{\dfrac12-\dfrac1{2^{n+1}}}{\dfrac12}\\ =\frac12\left(S-\frac{n-1}{2^n}\right)+1-\frac1{2^n}.$$

$\endgroup$
1
$\begingroup$

First, we observe the trivial equality $i=\sum_{j=1}^i (1)$. Using this, we can write

$$\begin{align} \sum_{i=1}^n \frac{i}{2^i}&=\sum_{i=1}^n \frac{\sum_{j=1}^i (1)}{2^i}\\\\ &=\sum_{i=1}^n \sum_{j=1}^i \frac{1}{2^i}\\\\ &=\sum_{j=1}^n \sum_{i=j}^n \frac{1}{2^i}\\\\ &=\sum_{j=1}^n \left(\frac{(1/2)^j-(1/2)^{n+1}}{1-1/2}\right)\\\\ &=2\sum_{j=1}^n (1/2)^j -2\sum_{j=1}^n(1/2)^{n+1}\\\\ &=2\left(\frac{(1/2)-(1/2)^{n+1}}{1-1/2}\right)-n(1/2)^n\\\\ &=2-(1/2)^n(n+2) \end{align}$$

as was to be shown!

$\endgroup$
1
$\begingroup$

$$\begin{align} S &=\sum_{i=1}^n \frac i{2^i} &&=\quad\frac 1{2^1}+\frac 2{2^2}+\frac 3{2^3}+\frac 4{2^4}+\cdots+\frac {n-1}{2^{n-1}}+\frac n{2^n}\tag{1}\\ 2S &= &&\frac 1{2^0}+\frac 2{2^1}+\frac 3{2^2}+\frac 4{2^3}+\frac 5{2^4}+\cdots +\frac n{2^{n-1}}\tag{2}\\ (2)-(1):\hspace{3cm}\\ S &= &&\underbrace{\frac 1{2^0}+\frac 1{2^1}+\frac 1{2^2}+\frac 1{2^3}+\frac 1{2^4}+\cdots+\frac 1{2^{n-1}}}_{\text {GP: }\ \ a=1,\ \ r=\frac 12}-\frac n{2^n}\\ &= &&\frac {\;\;1-\left(\frac 12\right)^n}{1-\frac 12}-\frac n{2^n}\\ &= &&\color{red}{2-\frac {n+2}{2^n}} \end{align}$$

$\endgroup$
0
$\begingroup$

Let $A=\sum_{k=1}^n \frac i {2^j}$. If you want to prove that $A<2$, this approach is natural: (i) you try to evaluate your sum; (ii) you take the difference from 2, and hope it is positive. In this case is a neat $\frac {n+2}{2^n}$, so it is good.

(Aside:) That the denominator is $2^n$, is clear. The real computation is the numerator. But you can convince yourself it is a linear polynomial, from the rate of convergence of the series $\sum_{j=1}^\infty \frac j {2^j}$.

(Extra:) I know it is not required in your question to prove (2), but for completeness I write up my favourite way of doing it. Consider the polynomial $1+x+\ldots+x^n=\frac {x^{n+1}-1}{x-1}$. Take the derivative: $$1+2x+\ldots +nx^{n-1}=\frac{(n+1)x^n(x-1)-(x^{n+1}-1)}{(x-1)^2}.$$ Plug in $x=\frac 1 2$, multiply all by $\frac 1 2$, and you have it. Do you see how does the linear term $n$ appear in the numerator? Whereas the main term $2=\frac 1 2 \frac {1}{(x-1)^2}$ is there because the other terms, that contain $x^n$, are typically very small, so they contribute to the "error term".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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