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$

Question

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$$

Answer 1

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$.

1. $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.
2. $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.
3. $|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}$$

Answer 2

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)$.