Estoy tratando de demostrar por inducción que el número de subconjuntos de un conjunto es igual a $2^n$. Voy a empezar con la base de caso cuando n=1, por ejemplo, y el número de subconjuntos es claramente 2. Cuando vamos para n=2, el número de subconjuntos aumenta a 4, y puedo ver que de esta manera: el subconjunto vacío sigue ahí, el subconjunto que tiene todos los elementos todavía está allí, el número de subconjuntos que tienen sólo 1 elemento se incrementa en 1, ya que añadir otro elemento, no estoy seguro acerca de los conjuntos que tienen varios elementos en ellos (esto es para $n \geq 3$; tiene que ver con $\textrm{C}$ombinations? ¿Cómo puedo escribir un matemáticamente riguroso inductivo prueba de esto? Gracias!
Respuestas
¿Demasiados anuncios?
El truco habitual es suponer que la afirmación es verdadera para $n$, y deje $A$ ser un conjunto de $n+1$ elementos.
Recoger algunas $a\in A$, y deje $A'=A\setminus\{a\}$. Por la hipótesis de inducción $A'$ tiene exactamente $2^n$ subconjuntos.
Para cada subconjunto de $A'$ hemos partido de un subconjunto de a $A$ $a$ en la misma, por: $B\subseteq A'\mapsto B\cup\{a\}$. Esta es una función inyectiva y desde $a\notin A'$$B\neq B\cup\{a\}$.
Tenga en cuenta que tanto $B$ $B\cup\{a\}$ son subconjuntos de a $A$. En particular, hemos encontrado $2\times 2^n$ subconjuntos. Tenemos que demostrar que no hay otros.
Deje $C\subseteq A$ ser algún subconjunto, si $a\notin C$ a continuación, se contó $C$ como un subconjunto de a $A'$, y si $a\in C$ $C\setminus\{a\}$ fue contado como un subconjunto de a $A'$ y fue asignada a $C$ mediante la adición de $a$.
Esto demuestra que no son exactamente $2\times 2^n = 2^{n+1}$ subconjuntos de un conjunto de tamaño $n+1$.
Ollie Treend
Puntos
11
Usted piensa de cada subconjunto como una cadena binaria de 0's y 1's, donde el $i^{th}$ carácter de la cadena es 0 si $i^{th}$ elemento en el conjunto no está en el subconjunto.
Así que para su Inductivo Hipótesis, se supone que hay $2^k$ único cadenas binarias de longitud $k$, por lo que ahora usted tiene que demostrar que hay $2^{k+1}$ único cadenas binarias de longitud $k+1$.
Para mostrar que hay el doble de cadenas binarias de longitud $k+1$ de la longitud de la $k$. (Os dejo esta parte de ustedes, ya que es probablemente la tarea)
Josef Pfleger
Puntos
37003
Para mostrar que el número de subconjuntos de un conjunto con $n$ elementos es $2^{n}$, vamos a utilizar una combinatoria de la prueba. Sabemos que el coeficiente binomial está dada por $\frac{n!}{k!(n-k)!}= {n \choose k}$, esto a su vez es el número de $\{A \subset \{1,..,n\}\}$, es decir, el número de subconjuntos de a$A$$\{1,...n\}$.
Una de las propiedades del coeficiente binomial es la siguiente: $(a+b)^{n}=\sum_{k=0}^{n} {n \choose k}a^{k}b^{n-k}$. Ya queremos conocer a $how$ muchos subconjuntos $A$ de un conjunto $\{1,...,n\}$ no son, sencillamente, se suma el número de subconjuntos de a$A$$\{1,...,n\}$, es decir, $\sum_{k=0}^{n}{n \choose k}$ donde $a=b=1$. Por lo tanto, $\sum_{k=0}^{n}{n\choose k}=(1+1)^{n}=2^{n}$.
