Prueba combinatoria para $2^n=1+\sum_{k=0}^{n-1}2^k$

Question

Estoy tratando de encontrar una prueba por doble conteo.

Lógicamente en cuanto a la parte izquierda estaba pensando en el número de todos los subconjuntos de un conjunto n.

En el lado derecho siguiendo la misma lógica veo que con la misma lógica esto se traducirá en sumar el número de subconjuntos de todos los k-conjuntos para k=0 a n-1 y luego añadir un conjunto más.

Esto parece un poco contraintuitivo, ya que hay muchos conjuntos que se contarán doble.

Me fijé en la construcción de los subconjuntos de k a k+1 e intenté encontrar una relación de recurrencia.

Me he dado cuenta de que, de hecho, el número de subconjuntos de un conjunto n es igual a la cantidad de subconjuntos de n=0 a n-1 sumados más 1. Pero no entiendo por qué es cierto.

Para mí tiene más sentido que $2^n$ es igual a la suma de todos los subconjuntos de longitud $k=0$ a $n-1$ y luego añadiendo el propio conjunto así más 1 y teniendo así $2^n=1+\sum_{k=0}^{n-1}\binom{n}{k}$ .

Estoy bastante seguro de que podríamos llegar a partir de esos coeficientes binomiales a la $2^k$ que queremos encontrar. Pero esto ya no sería una prueba de doble recuento.

¿Quizá tengo que ver el problema desde otro ángulo?

Answer 1

Pista: contar el número de subconjuntos de $\{1,2,...,n\}$ . Primero considere que en su elección para cada subconjunto, puede elegir si ( $2$ opciones) para incluir cada una de las $n$ lo que le proporciona $2^n$ . A continuación, considere la posibilidad de fijar el tamaño del subconjunto, digamos $k$ y para cada $k$ ver cuántos subconjuntos puede elegir, y luego sumar como $k$ atraviesa $1,2,...,n$ .

Answer 2

Contemos el número de subconjuntos de $\{0,1,2,...,n\}$ .

En el LHS, es $2^n$ porque cada elemento es o no es miembro de un subconjunto, y hacer esa elección para cada elemento conduce a un subconjunto diferente.

En el lado derecho, contamos los subconjuntos en función de su elemento mayor. El conjunto vacío es un valor atípico, por lo que lo contamos por separado. A partir de ahí, hay $2^0$ subconjuntos cuyo mayor elemento es $1$ (sólo $\{1\}$ ), $2^1$ subconjuntos cuyo mayor elemento es $2$ (ambos $\{2\}$ et $\{1,2\}$ ), y en general $2^k$ subconjuntos cuyo mayor elemento es $k+1$ .

Por lo tanto, $$2^n=1+\sum_{k=0}^{n-1}2^k$$

Answer 3

Contemos todos los subconjuntos no vacíos de $\{1,2,\ldots,n\}$ dos veces.

Obtenemos $2^n - 1$ mediante el argumento estándar de que podemos incluir el elemento $i$ en un subconjunto o no (dar es $2^n$ opciones, por $n$ opciones independientes) y restándole el conjunto vacío (el $-1$ ).

Sea (para $k=1,\ldots,n$ ) la colección $A_k$ sean todos los subconjuntos $A$ de $\{1,2,\ldots,n\}$ con $\max(A) = k$ . Para diferentes $k$ estos conjuntos son disjuntos: un conjunto finito no vacío tiene un único máximo; no puede ser a la vez $i$ et $j$ donde $i \neq j$ y todo conjunto no vacío tiene un máximo en $\{1,\ldots,n\}$ por lo que estos forman una partición.

Y $|A_k|= 2^{k-1}$ porque para formar un conjunto en $A_k$ ponemos $k$ (el máximo) en $A$ y luego tomar cualquier subconjunto de $\{1,\ldots,k-1\}$ (vacío para $k=1$ pero siempre hay $2^{k-1}$ subconjuntos del mismo) y añadirlo a $A$ y todos $A \in A_k$ puede hacerse así, de forma única.

Así que $$2^n -1 = \sum_{k=1}^n 2^{k-1}= \sum_{k=0}^{n-1}2^k$$

por una reindexación en la última suma. Ahora tira el 1 hacia el otro lado.

Alternativamente añadir el conjunto vacío como un singleton en la partición de todos los subconjuntos de $\{1,\ldots,n\}$ para obtener directamente la fórmula.

Answer 4

Consideremos el conjunto de secuencias binarias que no son la secuencia cero $(x_1,\dotsc, x_n)$ de longitud $n$ . Existen $2^n-1$ tales secuencias binarias. Ahora dividimos este conjunto en conjuntos $A_k$ en función de la posición $k$ que el primer $1$ se produce. Entonces $|A_k|=2^{n-k}$ para $k=1,\dotsc, n$ de lo que se deduce el resultado.