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

• Are you interested in my answer? Do not worry about the down vote. They are some irresponsible people. – Mhenni Benghorbal Jun 25 '13 at 13:53
• Here is an algebraic proof. Consider the series $$\sum_{k=0}^{n}x^k = \frac{1-x^{n+1}}{1-x}.$$ Diff. w.r. to $x$ gives $$\sum_{k=1}^{n}k x^{k-1}=\dots.$$ – Mhenni Benghorbal Jun 25 '13 at 14:37

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

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

• Note sure what that picture looked like when you posted it, but I can't figure it out. – Thomas Andrews Jun 25 '13 at 14:45
• @P..: another interpretation would be to sum the sum on the left by taking the tiles and arranging them the way that I showed. – Willie Wong Jun 25 '13 at 14:59
• @ThomasAndrews: is this picture better? – Willie Wong Jun 25 '13 at 15:00

Combinatoric interpretation.

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

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

• This appears to count the sum, but does not prove that it equals the desired $(n-1)2^n$. – vadim123 Jun 25 '13 at 14:13
• @vadim123, you are right. As for me: to use any common mathematical method. – Oleg567 Jun 25 '13 at 14:14
• just edited with combinatorial proof, as I see. – Oleg567 Jun 25 '13 at 14:29

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