Seeking a combinatorial proof of the identity $1+2\cdot 2^1+3\cdot 2^2+\cdots+n\cdot 2^{n-1}=(n-1)2^n+1$ I would appreciate if somebody could help me with the following problem
Q: show that combinatoric identity (using by combinatorial proof)
$$1+2\cdot 2^1+3\cdot 2^2+\cdots+n\cdot 2^{n-1}=(n-1)2^n+1$$
 A: Denote $\left[n\right]=\left\{1,\dots,n\right\}$. Count all pairs $\left(X,k\right)\in2^{\left[n\right]}\times\left[n\right]$ where $k\le\max X$ in two ways.
First way: First select $\max X$, then select $k$ and the rest of $X$.
Second way: Count all pairs in $2^{\left[n\right]}\times\left[n\right]$, then subtract the "bad" ones. Note that there is a matching between bad pairs $\left(X,k\right)$ and a non-empty sets $\emptyset\ne Y\subseteq\left[n\right]$ by $\left(X,k\right)\mapsto X\cup\left\{k\right\}$ and $Y\mapsto \left(Y\backslash\left\{\max Y\right\},\max Y\right)$.
A: We do this by double counting the number of tiles in a room that is $2^{n}$ tiles wide and $n-1$ tiles deep. The naive count would just be
$$ \text{depth} \times \text{width} = (n-1) 2^n $$
The second counting method is this: first divide the room into two sections, each of width $2^{n-1}$. The right section we divide into $n-1$ strips of $2^{n-1}$ tiles. The left section we remove one more strip of $2^{n-1}$ tile to be left with a rectangle of $(n-2) \cdot 2^{n-1}$ tiles. So we have gotten
$$ (n-1) \cdot 2^n = (n-1) \cdot 2^{n-1} + 1\cdot 2^{n-1} + (n-2)\cdot 2^{n-1} = n \cdot 2^{n-1} + (n-2) \cdot 2^{n-1} $$
repeat the procedure we expand the right hand side to get the sum desired. 
A picture for $n = 5$ looks something like
$$ \begin{array}{cc}
\color{red}{\Box\Box} \color{blue}{\Box\Box} \color{green}{\Box\Box\Box\Box}
~\color{grey}{\Box\Box\Box\Box\Box\Box\Box\Box}& \color{red}{\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box} \\
\color{grey}{\Box\Box\Box\Box}\color{black}{\Box\Box\Box\Box}~\color{blue}{\Box\Box\Box\Box\Box\Box\Box\Box} & \color{green}{\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box} \\
\color{red}{\Box\Box\Box\Box\Box\Box\Box\Box} ~\color{green}{\Box\Box\Box\Box\Box\Box\Box\Box} & \color{grey}{\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box} \\
\color{blue}{\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box} &\color{black}{\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box\Box}
\end{array}$$
A: Combinatoric interpretation.
Sub-task:

There is a ordered sequence (array, vector, chain, cortege, ...) of $k$ balls.
1 ball $-$ red, other balls $-$ black or white.
Let $M(k)$ $-$ number of such arrays.  
$M(k) = k \cdot 2^{k-1}$.
Example for $k=3$:
$\Huge{\color{red}\bullet} \circ\circ$,
$\Huge{\color{red}\bullet} \circ\bullet$,
$\Huge{\color{red}\bullet} \bullet\circ$,
$\Huge{\color{red}\bullet} \bullet\bullet$;

$\Huge{\circ\color{red}\bullet} \circ$,
$\Huge{\circ\color{red}\bullet} \bullet$,
$\Huge{\bullet\color{red}\bullet} \circ$,
$\Huge{\bullet\color{red}\bullet} \bullet$;
$\Huge{\circ\circ\color{red}\bullet}$,
$\Huge{\circ\bullet\color{red}\bullet}$,
$\Huge{\bullet\circ\color{red}\bullet}$,
$\Huge{\bullet\bullet\color{red}\bullet}$.
Task:

To find $S(n)$: number of all possible arrays (with 1 red and other black/white balls)  with length $k\leqslant n$.
$S(n) = M(1)+M(2)+\ldots+M(n)$.

How to prove:
Let $L(k)$ $-$ number of arrays, where red ball is on the $k$-th place:

$L(1) = 1+2+4+\cdots+2^{n-1} = 2^n-1$;
$L(2) = 2+4+\cdots+2^{n-1} = 2^n-2^1$;
$\ldots$
$L(k) = 2^{k-1}+2^k+\cdots+2^{n-1} = 2^n-2^{k-1}$;
$\ldots$
$L(n-1) = 2^{n-2}+2^{n-1} = 2^n-2^{n-2}$;
$L(n) = 2^{n-1} = 2^n-2^{n-1}$.
So, 
$$
S(n) = \sum_{k=1}^n L(k) = \sum_{k=1}^{n} (2^n - 2^{k-1}) = n2^n - (2^n-1) = (n-1)2^n+1.
$$
A: Let's denote by $[n]$ the set $\{1,2,\ldots\}$ and by  $\phi_{n,m}$ the set 
$$\left\{f:[n+1]\rightarrow [m]\mid f(i)\in [2], \ \forall i=1,2,\ldots n, \ f(n+1)\in [m]\right\}$$
i.e. all functions $f$ with domain $[n+1]$ and the property $f(i)\in\{1,2\}$ for all $i=1,2,\ldots,n$ and $f(n+1)\in[m]$. Then it is easy to see that the cardinality of $\phi_{n,m}$ is $|\phi_{n,m}|=2^n\cdot m$ and the identity to be proved is $$|\phi_{n,n-1}|=|\phi_{n-1,n}|+|\phi_{n-2,n-1}|+\ldots+|\phi_{1,2}|.$$
It's not hard to show the following properties for $\phi_{n,m}$: 


*

*$|\phi_{n,m}|=|\phi_{n-1,2m}|$ and 

*$|\phi_{n,m_1+m_2}|=|\phi_{n,m_1}|+|\phi_{n,m_2}|$ 


for all $n,m,m_1,m_2\in\mathbb N$.
Therefore $$|\phi_{n,n-1}|=|\phi_{n-1,2n-2}|=|\phi_{n-1,n}|+|\phi_{n-1,n-2}|=|\phi_{n-1,n}|+|\phi_{n-2,2n-4}|=\\
|\phi_{n-1,n}|+|\phi_{n-2,n-1}|+|\phi_{n-2,n-3}|=\ldots=|\phi_{n-1,n}|+|\phi_{n-2,n-1}|+\ldots+|\phi_{1,2}|.$$
