# How to compute the formula $\sum \limits_{r=1}^d r \cdot 2^r$?

Given $$1\cdot 2^1 + 2\cdot 2^2 + 3\cdot 2^3 + 4\cdot 2^4 + \cdots + d \cdot 2^d = \sum_{r=1}^d r \cdot 2^r,$$ how can we infer to the following solution? $$2 (d-1) \cdot 2^d + 2.$$

Thank you

• Commented Sep 23, 2017 at 7:31

There are at least five ways:

1. Use plain induction.
2. Differentiate the identity for the sum of a geometric series.
3. Find some combinatorial interpretation for both sides and provide a bijection.
4. Write as a sum of geometric series, sum each individual series, and sum the resulting geometric series.
5. Divide both sides by $2^d$ and slightly modify the sum so that it has some probabilistic interpretation. Use known properties of the relevant random variable.

As noted above, observe that \begin{eqnarray} \sum_{r = 1}^{d} x^{r} = \frac{x(x^{d} - 1)}{x - 1}. \end{eqnarray} Differentiating both sides and multiplying by $x$, we find \begin{eqnarray} \sum_{r = 1}^{d} r x^{r} = \frac{dx^{d + 2} - x^{d+1}(d+1) + x}{(x - 1)^{2}}. \end{eqnarray} Substituting $x = 2$, \begin{eqnarray} \sum_{r = 1}^{d} r 2^{r} = d2^{d + 2} - (d+1) 2^{d+1} + 2 = (d - 1) 2^{d+1} + 2. \end{eqnarray}

• Please see Yuval's #2 and Bill's answer. Commented Nov 23, 2010 at 18:14
• Note that this follows precisely the hint I gave 12 hours prior (alas, leaving no work for the OP). Commented Apr 22, 2012 at 16:11
• Bill, I hadn't even read your answer when I posted this. I like to do my own mathematics, thanks. Commented Apr 22, 2012 at 17:57

Perhaps a sixth way...

$$\displaystyle S = \sum_{r=1}^{d} r\cdot 2^r$$

$$\displaystyle 2S = \sum_{r=1}^{d} r\cdot 2^{r+1} = \sum_{r=2}^{d+1} (r-1)2^{r}$$

$$\displaystyle 2S -S = d\cdot 2^{d+1} - \sum_{r=1}^{d} 2^r = d\cdot 2^{d+1} - 2^{d+1} +2 = (d-1)2^{d+1} + 2$$

• "[T]he argument that follows may be one sixteenth proof for this theorem" (Thierry Coquand, Tiling Rectangles) Commented Nov 23, 2010 at 7:00

HINT $\displaystyle\rm\ \ \ r\ x^r\ =\ x \frac{d}{dx} (x^r)\:.\$ Apply this to $\rm\ \sum_{r=1}^d x^r\$ then put $\rm\ x = 2\:$.

This is an arithmetic-geometric progression. I remember doing these at school, I think even before O-levels. The typical A-G progression has the form $$ab,ar(b+d),ar^2(b+2d),\ldots,a r^n(b+nd)\ldots$$ (it's the pointwise product of an arithmetic progression and a geometric progression). To obtain the sum of the first $N$ terms, one uses the same trick as for summing $N$ terms of a GP. Let $$S=\sum_{k=0}^{N-1} ar^k(b+kd).$$ Then $$rS=\sum_{k=0}^{N-1} ar^{k+1}(b+kd)=\sum_{k=1}^N ar^k(b+kd-d).$$ Hence $$(1-r)S=ab-ar^N(b+(N-1)d)+\sum_{k=1}^{N-1}adr^k.$$ The last sum is that of a GP, which one already knows about...

• I found your comment in the first paragraph interesting as I believe we are of the same generation and my school never touched on AP's or GP's (let alone A-G progressions) until after O-levels. Commented Nov 23, 2010 at 8:40
• It's all such a long time ago... Commented Nov 23, 2010 at 11:58
• @Derek, @Robin: What's O-level in US terms? Commented Nov 24, 2010 at 3:52
• Being unAmerican, I have no idea. Commented Nov 24, 2010 at 7:32

You can use iterative integration of finite differences. The method works as follows. Assume your problem statement is:

$$\sum^n_{r=1} a_r = ?$$

Assume there is a function $S_n$ such that:

$$\sum^n_{r=1} a_r = S_n - S_1 + c$$

By finite difference we have:

$$a_n = \sum^n_{r=1} a_r - \sum^{n-1}_{r=1} a_r = (S_n - S_1 + c) - (S_{n-1} - S_1 + c) = S_n - S_{n-1} = \Delta S_n$$

Now assume we have a guess $T_n$ for $S_n$ such that some error $S'_n$ remains:

$$S_n = T_n + S'_n$$

The error itself can be expressed as a new integral since finite difference distributes over sums. We have:

$$a_n = \Delta S_n = \Delta T_n + \Delta S'_n$$

And hence we have a new sub problem:

$$\sum^n_{r=1} a'_r = \sum^n_{r=1} (a_r - \Delta T_r) = S'_n - S'_1 + c$$

Lets apply the method to the problem at hand, we have:

$$a_r = r\cdot 2^r$$

We can guess:

$$T_n = n\cdot 2^{n+1}$$

We arrive at:

$$a'_r = r\cdot 2^r - (r\cdot 2^{r+1} - (r - 1) \cdot 2^{r-1+1}) = - 2^r$$

We can guess again:

$$T'_n = - 2^{n+1}$$

We arrive at:

$$a''_r = - 2^r - (- 2^{r+1} - - 2^{r-1+1}) = 0$$

So the integration terminated, and the closed form integral is:

$$S_n = T_n + T'_n = n\cdot 2^{n+1} - 2^{n+1}$$

Using this for the sum we get:

$$\sum^n_{r=1} r\cdot 2^r = S_n - S_1 + c = n\cdot 2^{n+1} - 2^{n+1} - (1\cdot 2^{1+1} - 2^{1+1}) + c = 2\cdot (n - 1)\cdot 2^n + c$$

For $c$ we get:

$$\sum^1_{r=1} r\cdot 2^r = 2 = 0 + c$$

Saw this already in the 1980's in computer algebra systems (CAS), simpler than Gosper's method and different scope.

Bye

• P.S.: Used $\Delta f(x) = f(x) - f(x - 1)$, other authors might use $\Delta f(x) = f(x + 1) - f(x)$.
– user4414
Commented Oct 24, 2011 at 19:51

Denote the solution by $\rm\:S(d)\:,$ and put $\rm\ s(d) = S(d)/2 - 1 = (d-1)\:2^d\:.\$ It is the unique solution of the recurrence $\rm\ s(2) = 4,\ \ s(d+1)/s(d) = 2d/(d-1)\ \:$ i.e. $\rm\ (d-1)\ s(d+1)\ =\ 2d\ s(d)\:.\:$ It suffices to verify that $\rm\ sum/2 - 1$ satisfies the same recurrence - a simple calculation (probably essentially the same calculation that is in Moron's answer, but I haven't checked that).

REMARK $\$ This is a prototypical instance of the fact that uniqueness theorems provide very powerful tools for proving equalities. For many examples of such see some of my prior posts.

Have a look at Kelley and Peterson's textbook[1]. I think this book can give you a little more understanding of where everything comes from. It talks about difference calculus, which is the discrete analogue of continuous calculus. In difference calculus, we have the delta and sum operators where we have the derivative and integral respectively in continuous calculus.

Take a look at it and let me know if it helps.

[1] Kelley, W. & Peterson, A. (2001). Difference Equations: An Introduction with Applications (2nd Ed.). San Diego, CA: Academic Press.

Summation by parts gives that with the choice $a_k=2^k, b_k=k$ we have $$A_k = 2^1+\ldots+2^k = 2^{k+1}-2$$ and $$\sum_{k=1}^{n}a_k b_k = A_n b_n - \sum_{k=1}^{n-1} A_k$$ so: $$\sum_{k=1}^{n} k 2^k = (2^{n+1}-2)n-\sum_{k=1}^{n-1}(2^{k+1}-2) = (2^{n+1}-2)n+2(n-1)-2(2^n-2)$$ and the RHS simplifies to $(n-1) 2^{n+1}+2$ as wanted.