Todo conjunto tiene la misma cantidad de subconjuntos con número par e impar de elementos

Lo que se quiere decir es esto para cualquier n > 0:

\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots = \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+ \cdots

Demostración

No se tomará en cuenta el caso en el que n = 0 ya que sólo tiene una posibilidad que es \binom{0}{0} y necesitamos dos posibilidades como mínimo para establecer la igualdad.

Se dividirá la demostración en tres casos, cuando n es 1, cuando es par (mayor que 0), y cuando es impar (mayor que 1).

Caso 1. n es 1

Podemos decir que:

\binom{1}{0} = \binom{1}{1}

Caso 2. n es impar mayor que 1

Si n es impar, entonces n-1 es par.

Si escribimos todos los coeficientes binomiales posibles para n-1 se vería de la siguiente forma:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1}

Y podemos decir que son en total n coeficientes binomiales diferentes, porque estamos contando desde 0 hasta n-1. Es decir, tiene un número impar de coeficientes binomiales (debido a que n es impar).

Usaremos la regla de Pascal :

\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}

Vamos a hacer parejas con los coeficientes binomiales que contienen n-1 para generar coeficientes binomiales con el término n, pero como tenemos número impar de sumandos nos sobrará uno. Hagámos parejas de tal forma que nos sobre el último término y apliquemos la propiedad anterior:

\textcolor{orange}{\binom{n-1}{0}+\binom{n-1}{1}}+\textcolor{red}{\binom{n-1}{2}+\binom{n-1}{3}}+\cdots+\textcolor{green}{\binom{n-1}{n-3}+\binom{n-1}{n-2}}+\binom{n-1}{n-1} = \textcolor{orange}{\binom{n}{1}}+\textcolor{red}{\binom{n}{3}}+\cdots+\textcolor{green}{\binom{n}{n-2}}+ \binom{n-1}{n-1}

Teniendo el conocimiento de que para cualquier n> 0, \binom{n}{n} = 1 podemos hacer lo siguiente:

\binom{n-1}{n-1} = \binom{n}{n}

Lo reemplazamos en nuestros términos:

\binom{n}{1}+\binom{n}{3}+\cdots+\binom{n}{n-2}+ \binom{n-1}{n-1} = \binom{n}{1}+\binom{n}{3}+\cdots+\binom{n}{n-2}+ \binom{n}{n}

Entonces tenemos que:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots+ \binom{n}{n}

Dejemos ese resultado para después y ahora hagamos parejas de tal forma que el primer término quede solo:

\binom{n-1}{0}+\textcolor{orange}{\binom{n-1}{1}+\binom{n-1}{2}}+\textcolor{red}{\binom{n-1}{3}+\binom{n-1}{4}}+\cdots+\textcolor{green}{\binom{n-1}{n-2}+\binom{n-1}{n-1}} = \binom{n-1}{0}+\textcolor{orange}{\binom{n}{2}}+\textcolor{red}{\binom{n}{4}}+\cdots+\textcolor{green}{\binom{n}{n-1}}

Usemos este conocimiento:

\binom{n-1}{0} = \binom{n}{0}

Reemplazamos:

\binom{n-1}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-1} = \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-1}

Entonces tenemos que:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1}=\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-1}

Por transitividad:

\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-1}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots+ \binom{n}{n}

Caso 3. n es par mayor que 0

Se maneja similar al caso anterior.

Si n es par, entonces n-1 es impar.

Si escribimos todos los coeficientes binomiales posibles para n-1 se vería de la siguiente forma:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1}

Y podemos decir que son en total n coeficientes binomiales diferentes, porque estamos contando desde 0 hasta n-1. Es decir, tiene un número par de coeficientes binomiales (debido a que n es par).

Usaremos la regla de Pascal:

\binom{n}{r} = \binom{n-1}{r-1}+\binom{n-1}{r}

Vamos a hacer parejas con los coeficientes binomiales que contienen n-1 para generar coeficientes binomiales con el término n, todos los sumandos tendrán pareja porque tenemos número par de términos. Hagámoslo y apliquemos la propiedad anterior:

\textcolor{orange}{\binom{n-1}{0}+\binom{n-1}{1}}+\textcolor{red}{\binom{n-1}{2}+\binom{n-1}{3}}+\cdots+\textcolor{green}{\binom{n-1}{n-2}+\binom{n-1}{n-1}} = \textcolor{orange}{\binom{n}{1}}+\textcolor{red}{\binom{n}{3}}+\cdots+\textcolor{green}{\binom{n}{n-1}}

Éste sería el resultado:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1}=\binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots+ \binom{n}{n-1}

Dejemos ese resultado para después y ahora hagamos parejas de tal forma que el primer y último término no tengan pareja:

\binom{n-1}{0}+\textcolor{orange}{\binom{n-1}{1}+\binom{n-1}{2}}+\textcolor{red}{\binom{n-1}{3}+\binom{n-1}{4}}+\cdots+\textcolor{green}{\binom{n-1}{n-3}+\binom{n-1}{n-2}}+\binom{n-1}{n-1} = \binom{n-1}{0}+\textcolor{orange}{\binom{n}{2}}+\textcolor{red}{\binom{n}{4}}+\cdots+\textcolor{green}{\binom{n}{n-2}}+\binom{n-1}{n-1}

Teniendo estas dos cosas en cuenta para cualquier n>0:

\binom{n-1}{0} = \binom{n}{0}, \quad \binom{n-1}{n-1} = \binom{n}{n}

Lo aplicamos:

\binom{n-1}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-2}+\binom{n-1}{n-1} = \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n-2}+\binom{n}{n}

Entonces tenemos que:

\binom{n-1}{0}+\binom{n-1}{1}+\binom{n-1}{2}+\cdots+\binom{n-1}{n-1} = \binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n}

Por transitividad:

\binom{n}{0}+\binom{n}{2}+\binom{n}{4}+\cdots+\binom{n}{n} = \binom{n}{1}+\binom{n}{3}+\binom{n}{5}+\cdots+ \binom{n}{n-1}

1 thought on “Todo conjunto tiene la misma cantidad de subconjuntos con número par e impar de elementos”

Leave a Comment

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *