Derive that $\sum_{k=0}^{n-1} k \ 2^{n-(k+1)} = 2^n-n-1$.

Question

$\sum_{k=0}^{n-1} k \ 2^{n-(k+1)} = 2^n-n-1$.

How does one show a sum like this?

Answer 1

There are many ways. Induction is one, and another uses a bit of calculus, but a direct calculation reducing it to sums of geometric series is also possible, starting like this:

$$\begin{align*} \sum_{k=0}^{n-1}k2^{n-(k+1)}&=\sum_{k=1}^{n-1}\sum_{i=1}^k2^{n-(k+1)}\\ &\overset{(1)}=\sum_{i=1}^{n-1}\sum_{k=i}^{n-1}2^{n-(k+1)}\\ &\overset{(2)}=\sum_{i=1}^{n-1}\sum_{k=i+1}^n2^{n-k}\\ &\overset{(3)}=\sum_{i=1}^{n-1}\sum_{\ell=0}^{n-(i+1)}2^\ell \end{align*}$$

$(1)$ is just reversing the order of summation, analogous to reversing the order of integration; $(2)$ is shifting the index of the inner summation up by $1$; and $(3)$ is substituting $\ell=n-k$ in the inner summation.

The inner summation is now a finite geometric series, which you should be able to sum, and once you’ve done that, you’ll find that completing the calculation is mostly just summing another finite geometric series.

Answer 2

Hint

Observe that your sum can be written as

$$S=2^{n-1}\sum_{k=1}^{n-1}k(\frac 12)^k$$

Consider $$F(x)=1+x+x^2+...+x^{n-1}=$$ $$\frac{1-x^n}{1-x}$$ $$F'(x)=\frac{x^{n-1}((n-1)x-1)}{(1-x)^2}$$

$$xF'(x)=x+2x^2+3x^3+...+kx^k+...$$

So, $$S=2^{n-2}F'(\frac 12)$$

Answer 3

Take $2^{n-2}$ outside the sum.
Use $\sum_0^{n-1}kx^{k-1}=\frac{d}{dx}\sum_0^{n-1}x^k=\frac{d}{dx}\frac{1-x^n}{1-x}$. Then let $x=\frac{1}{2}$ to finish off.

Answer 4

Here is a generalization: $$ \begin{align} \sum_{k=m}^{n-1}\binom{k}{m}2^{n-(k+1)} &=\sum_{k=m}^{n-1}\binom{k}{m}\left(2^{n-k}-2^{n-(k+1)}\right)\tag{1a}\\ &=\sum_{k=m}^{n-1}\binom{k}{m}2^{n-k}-\sum_{k=m+1}^n\binom{k-1}{m}2^{n-k}\tag{1b}\\ &=\sum_{k=m}^{n-1}\binom{k}{m}2^{n-k}-\sum_{k=m}^{n-1}\binom{k-1}{m}2^{n-k}-\binom{n-1}{m}+2^n[m=0]\tag{1c}\\ &=\sum_{k=m}^{n-1}\binom{k-1}{m-1}2^{n-k}-\binom{n-1}{m}+2^n[m=0]\tag{1d}\\ &=2\sum_{k=m-1}^{n-2}\binom{k}{m-1}2^{(n-1)-(k+1)}-\binom{n-1}{m}+2^n[m=0]\tag{1e} \end{align} $$ Explanation:
$\text{(1a)}$: $2^{n-(k+1)}=2^{n-k}-2^{n-(k+1)}$
$\text{(1b)}$: substitute $k\mapsto k-1$ in the right-hand sum
$\text{(1c)}$: handle the edge terms from the right-hand sum
$\text{(1d)}$: $\binom{k-1}{m-1}=\binom{k}{m}-\binom{k-1}{m}$
$\text{(1e)}$: substitute $k\mapsto k+1$ and pull a factor of $2$ out front
$\phantom{\text{(1e):}}$ so that the sum matches with $(n,m)\mapsto(n-1,m-1)$

Applying $(1)$ twice gives $$ \begin{align} \sum_{k=1}^{n-1}\binom{k}{1}2^{n-(k+1)} &=2\color{#C00}{\sum_{k=0}^{n-2}\binom{k}{0}2^{(n-1)-(k+1)}}-(n-1)\tag{2a}\\ &=2\color{#C00}{\left(2^{n-1}-1\right)}-(n-1)\tag{2b}\\[8pt] &=2^n-n-1\tag{2c} \end{align} $$ Explanation:
$\text{(2a)}$: apply $\text{(1e)}$
$\text{(2b)}$: apply $\text{(1e)}$ to the red part
$\text{(2c)}$: simplify