Closed form of $\sum_{k=0}^{n}k\cdot2^{n-k}$

Question

I am interested in solving the recurrence relation using iterative method. I know how to solve it using generating function and another method using solution of associated linear homogeneous recurrence relation and particular solution described in Rosen's Discrete Math book. I came up with some summation (below) but I don't know how to find its closed form. I checked WolframAlpha and it provided me with this $$\sum_{k=0}^{n}k\cdot2^{n-k}=-n+2^{n+1}-2$$ How to show this?

Answer 1

HINT:

$$\sum_{k=0}^nk2^{n-k}=2^n\sum_{k=0}^nk\left(\frac12\right)^k\;,$$

so you’re done if you can evaluate

$$f(x)=\sum_{k=0}^nkx^k$$

at $x=\frac12$. Start with $g(x)=\sum_{k=0}^nx^k$, differentiate, and multiply by $x$. (I’m assuming that you know a closed form for $g(x)$.)

Answer 2

First, once you have a candidate for the closed form, you can prove that it works using induction. Regarding your sum, note that is has the form

$$ c \sum_{k=0}^n k x^{k - 1} = c \left( \sum_{k=0}^n x^k \right)' = c \left( \frac{x^{n+1} - 1}{x - 1} \right)'. $$

Indeed, $c = 2^{n-1}$ and $x = \frac{1}{2}$.

Answer 3

You can see it as \begin{align} \sum_{k=0}^n k2^{n-k} = {} & 2^{n} \sum_{k=1}^n k2^{-k} \\ & \text{letting $x=\frac12$,} \\ = {} & \frac{1}{x^n} \sum_{k=1}^n kx^k = \frac{1}{x^{n-1}} \sum_{k=1}^n kx^{k-1} \end{align} We further divided by $x$ in the last equality so that $kx^{k-1}$ is exactly the derivative of $x^k$, which then makes it possible to get rid of the multiplying factor $k$ in each term $kx^k$ term. Indeed, let $$ F(x) = \sum_{k=1}^n kx^{k-1} $$ so that what you are looking for is $2^{n-1}F(1/2)$.

Now, as observed, $$ F'(x) = \sum_{k=1}^n x^k = \frac{1-x^{n+1}}{1-x} - 1 $$ where the $-1$ comes from the fact that we are summing from $k=1$ and not $k=0$. Now it's just a matter of integrating...

Answer 4

By induction:

$$S_{n+1}=2S_n+n+1,$$ as all terms are multiplied by $2^{n+1-k}$ instead of $2^{n-k}$, and there is an extra term $(n+1)\cdot2^{n-n}$.

On the other hand,

$$-(n+1)+2^{(n+1)+1}-2=2(-n+2^{n+1}-2)+n+1.$$

The base case $n=0$ is also verified:

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

Answer 5

Semi-graphically:

$$1\cdot16+2\cdot8+3\cdot4+4\cdot2+5\cdot1\\=\\ \begin{align} 16+8+4+2+1+&&\to&&{32-1}+\\ 8+4+2+1+&&\to&&{16-1}+\\ 4+2+1+&&\to&&{8-1}+\\ 2+1+&&\to&&{4-1}+\\ 1\ \ \ &&\to&&{2-1}+\\ &&\to&&{1-1}\ \ \ \end{align}\\ =\\(64-1)-6.$$

Then general pattern is $(2^{n+1}-1)-(n+1)$.

Graphically:

Answer 6

From $$ \sum_{k=0}^{n}x^{k}=\frac{1-x^{n+1}}{1-x}$$ differentiate to get$$ \sum_{k=0}^{n}kx^{k-1}=\frac{-nx^{n}\left(1-x\right)+1-x^{n}}{\left(1-x\right)^{2}}$$ Multiplying by $x$ so that $$ \sum_{k=0}^{n}kx^{k}=x\cdot\frac{-nx^{n}\left(1-x\right)+1-x^{n}}{\left(1-x\right)^{2}}$$ and replace $x$ by $\frac{1}{2}$, we get$$ \sum_{k=0}^{n}k\left(\frac{1}{2}\right)^{k}=-n2^{-n}+2-2^{-n+1}$$ Lastly, by multiplying $2^{n}$, $$ \sum_{k=0}^{n}k2^{n-k}=-n+2^{n+1}-2$$