# 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

-

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. –  Aryabhata Nov 23 '10 at 18:14
Note that this follows precisely the hint I gave 12 hours prior (alas, leaving no work for the OP). –  Bill Dubuque Apr 22 '12 at 16:11
Bill, I hadn't even read your answer when I posted this. I like to do my own mathematics, thanks. –  user02138 Apr 22 '12 at 17:57

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

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

-

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) –  Yuval Filmus Nov 23 '10 at 7:00

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. –  Derek Jennings Nov 23 '10 at 8:40
It's all such a long time ago... –  Robin Chapman Nov 23 '10 at 11:58
@Derek, @Robin: What's O-level in US terms? –  Bill Dubuque Nov 24 '10 at 3:52
Being unAmerican, I have no idea. –  Robin Chapman Nov 24 '10 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)$. –  j4n bur53 Oct 24 '11 at 19:51

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.

-

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.

-