Algorithms Sum of the Series I am studying for an algorithms test and having trouble with series. I haven't done series in a long time and it all went away from me. I have the steps but I am having trouble following one of the steps.
\begin{align*}
&\sum_{k=0}^n k 2^{n-k}\\
S=&\sum_{k=0}^n k 2^{n-k}\\
2S=&\sum_{k=0}^n k 2^{n-k+1}\\
\end{align*}
I don't understand how it transitions to this step which leaves me lost for the rest of the steps:
\begin{align*}
2S&=\sum_{k=0}^{n-1} (k+1) 2^{n-k}\\
S &= 2S - S = n - \sum_{k=0}^{n-1} 2^{n-k}\\
S&= -n + \sum_{k=1}^n 2^k\\
S&= -n + 2^{n+1} - 2\\
S&= 2^{n+1} - n - 2
\end{align*}
Why was the range shifted to "$k=-1$ to $n-1$" and where does the $+1$ come from on the $k$? 
If also someone could recommend a site where I can brush up on these concepts and these types of problem, that would also be appreciated.
Thanks in advance.
 A: 
Here are some aspects we could consider when looking at the sum
  \begin{align*}
S=\sum_{k=0}^n k 2^{n-k}\tag{1}
\end{align*}

We observe the factor $k$ increases the complexity of the sum $S$. The sum without the factor $k$
\begin{align*}
\sum_{k=0}^n2^{n-k}\tag{2}
\end{align*}
is easier to calculate. This easier sum reminds us on the finite geometric sum
\begin{align*}
\sum_{k=0}^n2^{k}=\frac{1-2^{n+1}}{1-2}=2^{n+1}-1\tag{3}
\end{align*}
We   observe a striking similarity of the sums in (2) and (3). Indeed, exchanging $k$  with $n-k$ transforms one  sum into the other by exchanging the order  of summation.
\begin{align*}
\sum_{k=0}^n2^{n-k}&=2^{n-0}+2^{n-1}+\cdots+2^{n-n}\\
&=2^{n}+2^{n-1}+\cdots+2^{0}\qquad\qquad\text{exchange }\quad k\longleftrightarrow n-k\\
&=2^{0}+2^{1}+\cdots+2^{n}\\
&=\sum_{k=0}^n2^k
\end{align*}

In the following we see a trick to get rid of the factor $k$. It is typical and we could try to incorporate it into the own repertoire.
When  we look at the sum $S$ we observe, that the first summand with $k=0$ is equal to $0$ providing no contribution to the sum. We can instead  start with the index $k=1$ and obtain
  \begin{align*}
S&=\sum_{k=1}^{n}k2^{n-k}\\
&=\sum_{k=0}^{n-1}(k+1)2^{n-k-1}\tag{4}\\
&=\frac{1}{2}\sum_{k=0}^{n-1}(k+1)2^{n-k}\\
&\\
2S&=\sum_{k=0}^{n-1}(k+1)2^{n-k}\tag{5}
\end{align*}

Comment:


*

*In (4) we shift the index $k$ by one just for convenience. You could do a plausability check of these representations by explicitly writing down the a few summands of them.

*In (5) we see a representation of $2S$ with the factor $k+1$ in the sum.

This is beneficial for us, since we can use the representation of 
  \begin{align*}
S=\sum_{k=0}^n k 2^{n-k}\qquad\text{and}\qquad 2S=\sum_{k=0}^{n-1}(k+1)2^{n-k}
\end{align*}
  to get rid of $k$ by subtracting these expressions. This way we get
  \begin{align*}
S&=2S-S\\
&=\sum_{k=0}^{n-1}(k+1)2^{n-k}-\sum_{k=0}^n k 2^{n-k}\\
&=\left(\sum_{k=0}^{n}(k+1)2^{n-k}-(n+1)\right)-\sum_{k=0}^n k 2^{n-k}\tag{6}\\
&=\sum_{k=0}^{n}2^{n-k}-(n+1)\tag{7}\\
&=2^{n+1}-n-2
\end{align*}

Comment:


*

*In (6) we add to the left sum the summand with index $k=n$ and subtract it.

*In (7) we apply the finite geometric sum formula (3).
