La búsqueda de una combinatoria prueba de la identidad de $1+2\cdot 2^1+3\cdot 2^2+\cdots+n\cdot 2^{n-1}=(n-1)2^n+1$

Question

Agradecería si alguien me podría ayudar con el siguiente problema

P: mostrar que combinatoric identidad (utilizando la combinatoria de prueba)

$$1+2\cdot 2^1+3\cdot 2^2+\cdots+n\cdot 2^{n-1}=(n-1)2^n+1$$

Answer 1

Denotar $\left[n\right]=\left\{1,\dots,n\right\}$. Recuento de todos los pares $\left(X,k\right)\in2^{\left[n\right]}\times\left[n\right]$ donde $k\le\max X$ en dos maneras.

Primer paso: en Primer lugar elija $\max X$, a continuación, seleccione $k$ y el resto de $X$.

Segunda forma: Recuento de todos los pares en $2^{\left[n\right]}\times\left[n\right]$, luego restar las "malas". Tenga en cuenta que hay una coincidencia entre el mal pares de $\left(X,k\right)$ y un no-vacío conjuntos de $\emptyset\ne Y\subseteq\left[n\right]$$\left(X,k\right)\mapsto X\cup\left\{k\right\}$$Y\mapsto \left(Y\backslash\left\{\max Y\right\},\max Y\right)$.

Answer 2

Hacemos esto mediante el doble de contar el número de fichas en una habitación que es $2^{n}$ azulejos de ancho y $n-1$ azulejos de profundidad. El ingenuo contar sólo sería $$ \text{depth} \times \text{width} = (n-1) 2^n $$

El segundo método de recuento es este: primero divide la habitación en dos secciones, cada una de anchura $2^{n-1}$. La sección de la derecha nos dividimos en $n-1$ tiras de $2^{n-1}$ azulejos. La sección izquierda quitamos uno más de la tira de $2^{n-1}$ de la baldosa a la izquierda con un rectángulo de $(n-2) \cdot 2^{n-1}$ azulejos. Así que hemos conseguido

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

repita el procedimiento se expanda el lado derecho para obtener la suma deseada.

Una imagen para $n = 5$ se ve algo como

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

Answer 3

Combinatoric interpretación.

Sub-tarea:
Hay una secuencia ordenada (matriz, vector, cadena, cortejo, ...) de $k$ bolas.
1 bola de $-$ rojo, otras bolas $-$ negro o blanco.

Vamos $M(k)$ $-$ el número de tales arreglos. $M(k) = k \cdot 2^{k-1}$.

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

Tarea:
Para encontrar $S(n)$: número de todas las posibles matrices (con 1 rojo y otro en negro/blanco pelotas) con una longitud de $k\leqslant n$.

$S(n) = M(1)+M(2)+\ldots+M(n)$.

---

Cómo probar:

Vamos $L(k)$ $-$ número de matrices, donde la bola roja es en el $k$-ésimo lugar:
$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}$.

Así, $$ 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. $$

Answer 4

Vamos a denotar por $[n]$ el conjunto $\{1,2,\ldots\}$ y $\phi_{n,m}$ el conjunto $$\left\{f:[n+1]\rightarrow [m]\mid f(i)\in [2], \ \forall i=1,2,\ldots n, \ f(n+1)\in [m]\right\}$$ es decir, todas las funciones $f$ dominio $[n+1]$ de la propiedad y el $f(i)\in\{1,2\}$ todos los $i=1,2,\ldots,n$$f(n+1)\in[m]$. Entonces es fácil ver que la cardinalidad de a $\phi_{n,m}$ $|\phi_{n,m}|=2^n\cdot m$ y la identidad de probar es $$|\phi_{n,n-1}|=|\phi_{n-1,n}|+|\phi_{n-2,n-1}|+\ldots+|\phi_{1,2}|.$$ No es difícil demostrar las siguientes propiedades de $\phi_{n,m}$:

• $|\phi_{n,m}|=|\phi_{n-1,2m}|$ y
• $|\phi_{n,m_1+m_2}|=|\phi_{n,m_1}|+|\phi_{n,m_2}|$

para todos los $n,m,m_1,m_2\in\mathbb N$. Por lo tanto $$|\phi_{n,n-1}|=|\phi_{n-1,2 n-2}|=|\phi_{n-1,n}|+|\phi_{n-1,n-2}|=|\phi_{n-1,n}|+|\phi_{n-2,2 n-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}|.$$