7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Are you interested in my answer? Do not worry about the down vote. They are some irresponsible people. $\endgroup$ – Mhenni Benghorbal Jun 25 '13 at 13:53
  • $\begingroup$ 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. $$ $\endgroup$ – Mhenni Benghorbal Jun 25 '13 at 14:37
7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.