Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

8 Answers

up vote 3 down vote accepted

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}

share|improve this answer
    
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
1  
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
add comment

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.
share|improve this answer
add comment

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

share|improve this answer
add comment

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

share|improve this answer
    
"[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
add comment

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

share|improve this answer
1  
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
add comment

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

share|improve this answer
    
P.S.: Used $\Delta f(x) = f(x) - f(x - 1)$, other authors might use $\Delta f(x) = f(x + 1) - f(x)$. –  Cookie Monster Oct 24 '11 at 19:51
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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