Solving summation $2n+2^2(n-1)+2^3(n-2)+....+2^n$ Can anyone help me with this summation? I tried to use the geometric series on this, but I can't use that.
$$2n+2^2(n-1)+2^3(n-2)+....+2^n$$
I am trying to do this for studying algorithms. Can we get a closed form for this ?
 A: All you have to find out is how to sum out $$\sum_{k=1}^n 2^k(n-k+1)$$
This unwinds as 
$$(n+1) \sum_{k=1}^n2^k-\sum_{k=1}^nk2^k$$
The first term is a geometric series. Can you find out what the second term is?
One way is to note that $$\sum_{k=1}^n x^k=x\frac{1-x^n}{1-x}$$
Now, differentiate and multiply by $x$ to get that 
$$\sum_{k=1}^n kx^k=x\cdot\frac{d}{dx}\left(x\frac{1-x^n}{1-x}\right)$$
After finding out what the right hand side is, plug $x=2$.
A: It actually is possible to use the formula for the sum of a geometric series, though it’s certainly not the quickest approach. Expand the series into a triangular array like this:
$$\begin{array}{cc}
2&+&2&+&2&+&\ldots&+&2&+&2&=&2n\\
&&2^2&+&2^2&+&\ldots&+&2^2&+&2^2&=&2^2(n-1)\\
&&&&2^3&+&\ldots&+&2^3&+&2^3&=&2^3(n-2)\\
&&&&&&\ddots&&\vdots&\vdots&\vdots\\
&&&&&&&&2^{n-1}&+&2^{n-1}&=&2^{n-1}\big(n-(n-2)\big)\\
&&&&&&&&&&2^n&=&2^n\big(n-(n-1)\big)
\end{array}$$
Now sum the columns to the left of the equals sign; each is a geometric series, so this isn’t hard. For $k=1,\dots,n$ the $k$-th column sum is
$$\sum_{i=1}^k2^i=2\sum_{i=0}^{k-1}2^i=2(2^k-1)=2^{k+1}-2\;,$$
so the original series is
$$\begin{align*}
\sum_{k=1}^n\left(2^{k+1}-2\right)&=2^2\sum_{k=0}^{n-1}2^k-2n\\\\
&=2^2(2^n-1)-2n\\\\
&=2^{n+2}-2(n+2)\;.
\end{align*}$$
You can also use a little calculus. Consider the function
$$f(x)=\sum_{k=1}^nx^k(n-k)\;;$$
you’re looking for $f(2)$. Now
$$\begin{align*}
f(x)&=n\sum_{k=1}^nx^k-\sum_{k=1}^nkx^k\\\\
&=nx\sum_{k=0}^{n-1}x^k-x\sum_{k=0}^{n-1}(k+1)x^k\\\\
&=\frac{n(x^n-1)}{x-1}-x\frac{d}{dx}\sum_{k=0}^nx^k\\\\
&=\frac{n(x^n-1)}{x-1}-x\frac{d}{dx}\left(\frac{x^{n+1}-1}{x-1}\right)\;,
\end{align*}$$
and a little straightforward calculus and algebra will finish off the general calculation.
A: This does have a nice closed form.
We can write your original sum, $2n+2^2(n-1)+2^3(n-2)+....+2^n$, as
$(2+2^2+2^3+...2^n)+(2+2^2+2^3+...2^{n-1})+2+2^2+2^3+...2^{n-2})+...+2$, because this sum will have $n$ $2$'s, $n-1$ $2^2$'s, and so on. By the geometric series formula, this sum simplifies to $(2^{n+1}-2) + (2^n-2) + (2^{n-1}-2)+...+(2^2-2)$, which itself simplifies (again by the geometric series formula) to $2^{n+2}-4-2n$.
A: Notice that 
$$S_n=2n+2^2(n-1)+2^3(n-2)+\cdots+2^{n-1}(2)+2^n(1)$$
$$S_{n-1}=2(n-1)+2^2(n-2)+2^3(n-3)+\cdots+2^{n-1}(1)+2^n(0)$$
differ by
$$S_n-S_{n-1}=2+2^2+2^3+\cdots+2^n=2(2^n-1)$$
Therefore, $$S_n=2(2^n-1) + S_{n-1} =2(2^n-1) + 2(2^{n-1}-1) + S_{n-2}$$and so on until
$$S_n=2(2^n-1 +2^{n-1}-1+2^{n-2}-1+\cdots+2^{1}-1)=2([2^1+2^2+\cdots+2^n]-n)$$
You should be able to figure out the answer.
A: Define 
$$s_n= \sum_{i=0}^{n-1}2^{i+1}(n-i)$$
and note that you have the relation:
$$S_{n+1}=S_n+2+2^2+\cdots+2^{n+1}=S_n+2^{n+2}-2$$ this comes from the fact that 
$$2^{i}(n-i)=2^{i}(n-i+1-1)=2^{i}(n-i-1)+ 2^i$$
Noting that : $S_1=2$ and that the solution of the simple recurrence above is:
$$S_{n+1}=S_1+2^3+\cdots^+2^{n+2}-2n=2^{n+3}-2^3+2-2n$$
Thus
$$S_{n}=2^{n+2}-2^3+2-2(n-1)$$ 
