# Smart demonstration to the formula $\sum_{n=1} ^{N} \frac{n}{2^n} = \frac{-N + 2^{N+1}-2}{2^n}$

Someone could give me a smart and simple solution to show the folowing identity?

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

-
Possible duplicate of math.stackexchange.com/questions/30732/… –  Eric Naslund Jan 1 '13 at 2:03
Please define 'smart' –  Alex Jan 1 '13 at 3:11

$$\sum_{n=1}^N \dfrac{n}{2^n}$$ can be written as \begin{matrix} \dfrac12 & + \dfrac1{2^2} & + \dfrac1{2^3} & + \dfrac1{2^4} & + \cdots & + \dfrac1{2^{N-1}} & + \dfrac1{2^N}\\ & + \dfrac1{2^2} & + \dfrac1{2^3} & + \dfrac1{2^4} & + \cdots & + \dfrac1{2^{N-1}} & + \dfrac1{2^N}\\ & & + \dfrac1{2^3} & + \dfrac1{2^4} & + \cdots & + \dfrac1{2^{N-1}} & + \dfrac1{2^N}\\ & & & + \vdots & + \vdots & + \vdots & + \vdots\\ & & & & & & + \dfrac1{2^N}\\ \end{matrix} Now sum them row wise to get $$\left(1 - \dfrac1{2^N} \right) + \dfrac12\left(1 - \dfrac1{2^{N-1}} \right) + \dfrac1{2^2}\left(1 - \dfrac1{2^{N-2}} \right) + \cdots + \dfrac1{2^{N-1}}\left(1 - \dfrac1{2} \right)\\ = \left(1 + \dfrac12 + \dfrac1{2^2} + \cdots + \dfrac1{2^{N-1}} \right) - \left(\dfrac1{2^N} + \dfrac1{2^N} + \dfrac1{2^N} + \cdots + \dfrac1{2^N} \right)\\ = 2 - \dfrac1{2^{N-1}} - \dfrac{N}{2^N}$$ Essentially, we are doing the following $$\sum_{n=1}^N \dfrac{n}{2^n} = \sum_{n=1}^N \sum_{k=1}^n \dfrac1{2^n} = \sum_{k=1}^N \sum_{n=k}^{N} \dfrac1{2^n} = \sum_{k=1}^N \dfrac1{2^{k-1}}\left(1 - \dfrac1{2^{N+1-k}}\right) = \sum_{k=1}^N \left(\dfrac1{2^{k-1}} - \dfrac1{2^{N}} \right)\\ = 2 - \dfrac1{2^{N-1}} - \dfrac{N}{2^N}$$

-
I see that there are often geometric interpretations of sums. Are there any profound summation techniques involving this kind of situation? I've seen general results regarding how to sum the same series (regardless of its argument) in different ways, but I haven't quite seen the geometric perspective. –  000 Jan 1 '13 at 2:41
@Limitless Could you expand on what you mean by a geometric perspective? Interchanging summation is equivalent to interchanging integrals in which case either way you compute the same area. –  user17762 Jan 1 '13 at 2:43
Pardon me if this is vague: Geometric perspective means that you take the summation's terms, arrange them in some sort of array (a straight line, a square, etc), and perform a sort of process based on this array. For example, you can prove the basic $\sum_{i\ge 0}i=\frac{i(i+1)}{2}$ using this perspective. –  000 Jan 1 '13 at 2:45
@Limitless:See mathdl.maa.org/images/cms_upload/268948749035.pdf [I got this from David Mitra's post from the link that Eric Naslund posted] –  Isomorphism Jan 1 '13 at 3:10

See the following answer: How can I evaluate $\sum_{n=0}^\infty (n+1)x^n$.

We can use a similar technique as that used to sum the geometric series $\sum_{n=1}^k r^n.$ Let $$S_{m}=\sum_{n=1}^{m}nr^{n},$$ and consider $$S_{m}-rS_{m}=-mr^{m+1}+\sum_{n=1}^{m}r^{n}.$$ Using our known formula for the geometric series, we find that $$S_m = \frac{mr^{m+2}-(m+1)r^{m+1}+r}{(1-r)^2}.$$
This equality holds for any $r\neq 1$, so inserting $r=\frac{1}{2}$ we have that $$\sum_{n=1}^N \frac{n}{2^n}=\frac{2^N+1-N+2}{2^N}$$

-
Elegant, to the point, and an extension of a simple result. +1 –  000 Jan 1 '13 at 2:37

\eqalign{\sum_{n=1}^N n r^n &= r \dfrac{d}{dr} \sum_{n=0}^n r^N \cr &= r \dfrac{d}{dr} \dfrac{1 - r^{N+1}}{1-r}\cr &= r \dfrac{-(N+1) r^N (1-r) + (1 - r^{N+1})}{(1 - r)^2}\cr}

-

Proceed by induction.

Base case is true with $N=1$.

Inductive (I replaced the actual sum with $\sum$): $$\frac{N+1}{2^{N+1}} + \sum^N = \sum^{N+1}$$ $$\frac{N+1}{2^{N+1}} + \frac{-N+2^{N+1}-2}{2^N} = \frac{-(N+1) + 2^{N+2}-2}{2^{N+1}}$$ $$\frac{N + 1 - 2N + 2^{N+2} - 4}{2^{N+1}} = \frac{-N-3+2^{N+2}}{2^{N+1}}$$ $$\frac{- N - 3 + 2^{N+2}}{2^{N+1}} = \frac{-N-3+2^{N+2}}{2^{N+1}}$$

Which is true, so the summation is true. This is a good general way for proving summation formulas.

-
I like the little sigma idea there. I have done $\sum_k f(k)$, but I have never been so bold as to do $\sum_{}^u$. –  000 Jan 1 '13 at 2:39
@Limitless, haha, thanks. –  George V. Williams Jan 1 '13 at 2:41

This another approach shown as a way to use the Online Encyclopedia of Integer Sequences database to help construct a solution. If you take the following from the summation formula $$n=(1)=\frac{1}{2^1}=\frac{1}{2^1}$$ $$n=(2)=\frac{1}{2^1}+\frac{2}{2^2}=\frac{4}{2^2}$$ $$n=(3)=\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}=\frac{11}{2^3}$$ $$n=(4)=\frac{1}{2^1}+\frac{2}{2^2}+\frac{3}{2^3}+\frac{4}{2^4}=\frac{26}{2^4}$$ Note the sequence in the numerator. Go to OEIS and type in the sequence $1,4,11,26$ This will take you to sequence A000295 This sequence gives the formula $$a(n)=2^n - n - 1$$ However this sequence and formula happen to have a different offset (the subscript of the first term in the sequence) than the formula given by the OP. [A000295] is the following sequence $0,1,4,11,26...$ and we want $1,4,11,26...$. Taking the difference between these two sequences gives another sequence $1,3,7,15,31,...$. Enter this sequence in [OEIS] and it will take you to A000225. You will see that the formula for this sequence is $$2^n-1$$ Adding the formulas for [A000295] $2^n-n-1$ plus [A000225] $2^n-1$ give the desired formula for the numerator of $$2^{n+1}-n-2$$ It is obvious that the sum of the sequence 0,1,4,11,26 and 1,3,7,15,31 gives the desired sequence of 1,4,11,26,… with offset 1. To develop the formula yourself note that the page for [A00295] also gives the generating function for the series of $$\frac{x^2}{(1-2x)(1-x)^2}$$ from which the Binet formula can be derived using partial fractions as follows $$\frac{x^2}{(1-2x)(1-x)^2}=\frac{A}{(1-2x)}+\frac{B}{(1-x)}+\frac{C}{(1-x)^2}$$

We end up with $$A(1-2x+x^2)+B(1-3x+2x^2)+C(1-2x)$$ \begin{bmatrix} 1 & 1 & 1 & 0 \\[0.3em] -2 & -3 & -2&0 \\[0.3em] 1&2&0&1 \end{bmatrix} Solving the matrix we get $A=1, B=0, C=-1$ \eqalign{\sum_{n=0}^N 2^n x^n}+0\eqalign{\sum_{n=0}^N n x^n}-\eqalign{\sum_{n=0}^N (n+1) x^n} yielding $2^{n+1}-n-1$ Or you can develop the generating function from the recurrence relation for this sequence. The same thing can be done with the series A00225 The page for [A00225] also gives the generating function for the series of $$\frac{x} {(1-2x)(1-x)}$$ from which the Binet formula can be derived using partial fractions as follows $$\frac{x}{(1-2x)(1-x)}=\frac{A}{(1-2x)}+\frac{B}{(1-x)}$$

We end up with $$A(1-x)+B(1-2x)$$ \begin{bmatrix} 1 & 1 & 0 \\[0.3em] -1 & -2 & 1 \end{bmatrix} Solving the matrix we get $A=1, B=-1$ \eqalign{\sum_{n=0}^N 2^n x^n}-\eqalign{\sum_{n=0}^N 1^n x^n} yielding $2^n-1$. So $$\frac{(2^n-n-1)+(2^n-1)}{2^n}=\frac{2^{n+1}-n-2}{2^n}$$

-