3

It is easy to show that

$$\sum_{m=1}^{n-1} m(n-m) 2^{m-1}=(n-3)2^n + n+3 \tag{1}$$

using induction if one knows that $\sum_{m=1}^n m 2^{m-1} = (n-1)2^n + 1.$

But I was only able to guess the right closed-form after much trial-and-error. Is there a way to arrive at $(1)$ if we didn't know the answer beforehand?

Ojas
  • 147
  • 1
    Just to make sure, which expression(s) did you want a non-inductive answer for? – Bruno B Jul 27 '23 at 13:09
  • @BrunoB Sorry for the confusion. I have editted the question to make this clear. – Ojas Jul 27 '23 at 13:30
  • 2
    Long-winded way: since $\sum_{m=1}^{n-1}x^{m-1}=\frac{1-x^{n-1}}{1-x}$, you can get $\sum_m(m-1)x^{m-2},,\sum_m(m^2-3m+2)x^{m-2}$ by differentiation. Now take $x=2$ viz. $mn-m^2=n-1+(n-3)(m-1)-(m^2-3m+2)$. – J.G. Jul 27 '23 at 13:37
  • @J.G. I had tried the differentiation trick but it wasn't working. Writing $mn-m^2$ in terms of $m-1$ and $(m-1)(m-2)$ is a clever idea. I will write this up. – Ojas Jul 27 '23 at 13:42

2 Answers2

2

$$1+2×2+3×4+4×8+\cdots+n×2^{n-1}\\ =1+2+4+\cdots+2^{n-1}\\ +2+4+8+\cdots+2^{n-1}\\ +4+8+\cdots+2^{n-1}\\ +\cdots+2^{n-1}\\ =(2^n-1)+(2^n-2)+(2^n-4)+\cdots+(2^n-2^{n-1})\\ =n×2^n-(1+2+4+\cdots+2^{n-1})\\ =n×2^n-(2^n-1)$$

Empy2
  • 50,853
1

Here is a systematic way to derive this identity.

We obtain \begin{align*} \color{blue}{\sum_{m=1}^{n-1}}\color{blue}{m(n-m)2^{m-1}} &=\sum_{m=0}^{n}m(n-m)2^{m-1}\tag{1}\\ &=n\sum_{m=0}^{n}m2^{m-1}-\sum_{m=0}^{n}m^22^{m-1}\\ &\,\,\color{blue}{=(n-1)\sum_{m=0}^nm2^{m-1}-2\sum_{m=0}^nm(m-1)2^{m-2}}\tag{2} \end{align*}

Comment:

  • In (1) we use the symmetry of the sum and extend the index region without changing anything since we are adding zeros only.

  • In (2) we rearrange the sums to apply differentiation to finite geometric series.

The left-hand sum of (2) is \begin{align*} \color{blue}{\sum_{m=0}^{n}m2^{m-1}}&=\left.\left(\frac{d}{dx}\sum_{m=0}^{n}x^m\right)\right|_{x=2}\\ &=\left.\left(\frac{d}{dx}\left(\frac{1-x^{n+1}}{1-x}\right)\right)\right|_{x=2}\\ &=\left.\frac{nx^{n+1}-(n+1)x^n+1}{(1-x)^2}\right|_{x=2}\\ &\,\,\color{blue}{=n2^{n+1}-(n+1)2^n+1}\tag{3} \end{align*}

The right-hand sum of (2) is \begin{align*} \color{blue}{\sum_{m=0}^{n}m(m-1)2^{m-2}}&=\left.\left(\frac{d^2}{dx^2}\sum_{m=0}^{n}x^m\right)\right|_{x=2}\\ &=\left.\left(\frac{d^2}{dx^2}\left(\frac{1-x^{n+1}}{1-x}\right)\right)\right|_{x=2}\\ &=\left.\left(-\frac{n(n+1)x^{n-1}}{1-x}-\frac{2(n+1)x^n}{(1-x)^2}+\frac{2\left(1-x^{n+1}\right)}{(1-x)^3}\right)\right|_{x=2}\\ &=n(n+1)2^{n-1}-2(n+1)2^n-2\left(1-2^{n+1}\right)\\ &\,\,\color{blue}{=n^22^{n-1}-3n2^{n-1}+2^{n+1}-2}\tag{4} \end{align*}

Putting (3) and (4) into (2) we obtain \begin{align*} \color{blue}{\sum_{m=1}^{n-1}m(n-m)2^{m-1}} &=(n-1)\left(n2^{n+1}-(n+1)2^n+1\right)\\ &\qquad-2\left(n^22^{n-1}-3n2^{n-1}+2^{n+1}-2\right)\\ &=\left(n^2-n\right)2^{n+1}-\left(n^2-1\right)2^n+n-1\\ &\qquad-n^22^n+3n2^n-2^{n+2}+4\\ &=-n2^{n+1}+2^n+n-1+3n2^n-2^{n+2}+4\\ &\,\,\color{blue}{=(n-3)2^n+n+3} \end{align*} and the claim follows.

Markus Scheuer
  • 108,315