Ayuda con esta demostración de Subconjuntos Propios
Demostrar que los subconjuntos propios de
$$S= \{ a_{1}, a_2,...,a_n\} \,\,\, son \,\,\, 2^{n}-1 \,\,\,en \,\,\,numero$$
1 Respuesta
Los subconjuntos propios son aquellos distintos del conjunto completo.
No sé que demostración tendrás en el libro o que cosas has estudiado para poder demostrarlo. Se puede hacer por el binomio de Newton por ejemplo.
Los subconjuntos de 0 elementos son 1, el conjunto vacío
Los de 1 elemento son n, uno por cada elemento
Los de 2 elementos son combinaciones de n tomadas de 2 en 2. C(n, 2)
Los de 3 elementos son combinaciones de n tomadas de 3 en 3. C(n, 3)
Y así sucesivamente hasta C(n,n)
Los de cero también se pueden expresare como C(n, 0) y los de uno son C(n, 1)
Luego el número total de subconjuntos es
C(n,0) + C(n,1) + C(n,2) + .....+ C(n,n)
Estos C(n, i) son los coeficientes del binomio de Newton elevado a la n. Y en concreto son los coeficientes de
(1+1)^n = 2^n
Luego el número total de subconjuntos es 2^n, entonces el número de subconjuntos propios es 1 menos, luego
Numero de subconjuntos propios = 2^n - 1
También se podría demostrar por inducción, pero es que no se si eso lo has estudiado ya.
hola valeroasm
disculpa me podrías ayudar con la demostración por medio de inducción por favor
muchas gracias
Pues por medio de inducción demostraremos que el número de subconjuntos totales es 2^n
i) Para n=1 se cumple pues los dos subconjuntos posibles son el vacío y el de 1 elemento.
Ii) Ahora supongamos que se cumple para n. Es decir:
Subconjuntos de {a1, a2, ...,an} = 2^n
Ahora añadimos el elemento a sub n+1.
Los conjuntos que se pueden formar son
1) Los que no tienen a sub n+1. Ya los tenemos, son 2^n
2) Los que tienen a sub n+1. Estos serán la unión de un subconjunto que no tiene a sub n+1 con el elemento a sub n+1. Luego son tantos como los conjuntos que tenemos arriba
Además está bien claro que no hay ningún subconjunto que sea a la vez de tipo 1 y tipo 2. Luego para n+1 elementos hay
2^n + 2^n = 2^n(1+1) = 2 · 2^n = 2^(n+1)
Y con eso queda demostrada la inducción que queríamos, que el número de subconjuntos total es 2^n. De ahí pasamos a decir que el número de subconjuntos propios es (2^n)-1
Y eso es todo.
