Seeking a combinatorial proof of the identity$n+(n-1)2^1+(n-2)2^2+\cdots+ 2\cdot 2^{n-2}+ 1\cdot 2^{n-1}=-n+2^{n+1}-2$ I would appreciate if somebody could help me with the following problem
Q: show that combinatoric identity (using by combinatorial proof)
$$n+(n-1)2^1+(n-2)2^2+\cdots+ 2\cdot 2^{n-2}+ 1\cdot 2^{n-1}=-n+2^{n+1}-2$$
 A: LHS and RHS give two ways of counting the number of bit-strings of length $n+1$ with at least two ones in them. Define:
$$M= \{(a_1,\dots,a_{n+1})\in \{0,1\}^{n+1} | \sum\limits_{i=1}^{n+1}a_i \geq 2\}$$
We prove, $\text{LHS}=|M|=\text{RHS}$.
RHS: Then:
$$M=\{0,1\}^{n+1}\setminus\{0\}^{n+1} \setminus \{(a_1,\dots,a_{n+1})\in \{0,1\}^{n+1} | \sum\limits_{i=1}^{n+1}a_i = 1\}$$
So 
$$|M|=2^{n+1}-1-(n+1)=-n+2^{n+1}-2$$
LHS: Define $B_k = \{(a_1,\dots,a_{n+1})\in A | \sum\limits_{i=1}^{k}a_i = 1 \wedge a_{k+1}=1 \}$ for $k=1,\dots,n$ and $B=\bigcup\limits_{k=1}^{n}B_k$.


*

*$M=B$. Proof: Let $a=(a_1,\dots,a_{n+1})\in M$, this implies, that $k=\min\{i\geq 1\mid a_k=1\}$ is well-defined. Check, that $a\in B_{k-1}$. The converse is clearly true.

*$B_k \cap B_l=\varnothing$ for $k\neq l$. Proof: Assume $a\in B_k\cap B_l$. Wlog, assume $k<l$, then:
$$1\overset{a\in B_l}{=}\sum\limits_{i=1}^{l}a_i\geq \sum\limits_{i=1}^{k+1}a_i = \sum\limits_{i=1}^{k}a_i+a_{i+1}\overset{a\in B_k}{=}1+1=2$$
This is a contradiction.

*$|B_k|=k\cdot 2^{n-k}$. Proof: $a_{k+1}$ is fixed. There are $k$ possibilities for $(a_1,\dots,a_k)$ (since exactly one of them is $1$) and $2^{(n+1)-(k+2)+1}=2^{n-k}$ possibilites for $(a_{k+2},\dots,a_{n+1})$. 


So:
$$|M|\overset{1)}{=}|B|=\left|\bigsqcup\limits_{k=1}^{n}B_k\right|\overset{2)}{=}\sum\limits_{k=1}^{n}B_k\overset{3)}{=}\sum\limits_{k=1}^{n}k\cdot 2^{n-k}$$
A: This question is actually very similar to that one, therefore my answer is also similar.
Denote $\left[n\right]=\left\{1,\dots,n\right\}$. Count all pairs $\left(X,k\right)\in2^{\left[n\right]}\times\left[n+1\right]$ where $X\ne\emptyset$ and $k>\max X$ in two ways.
First way: First select $\max X$, then select $k$ and the rest of $X$.
Second way: There is a match between such pairs and $\left\{Y\subseteq\left[n+1\right]\middle|\left|Y\right|\ge2\right\}$ by $\left(X,k\right)\mapsto X\cup\left\{k\right\}$ and $Y\mapsto\left(Y\backslash\max Y,\max Y\right)$.
