Closed form of $\sum_{k=0}^{n}k\cdot2^{n-k}$ 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?
 A: 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)$.)
A: 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.$$
A: 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:

A: 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}$.
A: 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...
A: 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$$ 
