Cómo demostrar esta identidad desde la combinatoria

Answer 1

Prueba 1: –

[matemáticas] \ displaystyle \ text {RHS} = (2) ^ n = (1 + 1) ^ n [/ matemáticas]

ahora, usando el teorema binomial para expandir [matemáticas] (1 + 1) ^ n [/ matemáticas] para obtener

[matemáticas] \ displaystyle (1 + 1) ^ n = \ sum_ {k = 0} ^ {n} \ binom {n} {k} 1 ^ {nk} 1 ^ {k} [/ matemáticas]

[matemáticas] \ displaystyle = \ sum_ {k = 0} ^ {n} \ binom {n} {k} \ veces 1 [/ matemáticas]

[matemáticas] \ displaystyle = \ sum_ {k = 0} ^ {n} \ binom {n} {k} [/ matemáticas]

[matemáticas] \ displaystyle = \ binom {n} {0} + \ binom {n} {1} + \ binom {n} {2} + \ cdots + \ binom {n} {n-1} + \ binom { n} {n} = \ text {LHS}. [/ math]

QED

---

Prueba 2: –

Usaremos el principio de inducción matemática,

así que vamos a ver [matemáticas] n = 1 [/ matemáticas]:

[matemáticas] \ displaystyle \ text {LHS} = \ binom {1} {0} + \ binom {1} {1} [/ matemáticas]

[matemáticas] \ displaystyle = \ frac {1!} {0! (1-0)!} + \ frac {1!} {1! (1-1)!} [/ matemáticas]

[matemáticas] \ displaystyle = 1 + 1 [/ matemáticas]

[matemáticas] \ displaystyle = 2 [/ matemáticas],

[matemáticas] \ text {RHS} = 2 ^ 1 = 2 [/ matemáticas],

[math] \ text {LHS} = \ text {RHS} [/ math], por lo que es cierto para [math] n = 1 [/ math].

ahora supongamos que es cierto para [math] n = k [/ math]:

[matemáticas] \ displaystyle \ binom {k} {0} + \ binom {k} {1} + \ binom {k} {2} + \ dots + \ binom {k} {k-1} + \ binom {k } {k} = 2 ^ k [/ matemáticas]

y finalmente, demostremos que es cierto para [math] n = k + 1 [/ math]:

Para hacer esto, explotaremos nuestra suposición, la regla de Pascal y estas identidades triviales:

[matemáticas] \ displaystyle \ binom {k} {0} = \ binom {k + 1} {0} [/ matemáticas] y [matemáticas] \ displaystyle \ binom {k} {k} = \ binom {k + 1} {k + 1}. [/ matemáticas]

Hagamoslo :

[matemáticas] \ displaystyle \ text {LHS} = \ binom {k + 1} {0} + \ binom {k + 1} {1} + \ binom {k + 1} {2} + \ cdots + \ binom {k +1} {k} + \ binom {k + 1} {k + 1} \ tag * {} [/ math]

[matemáticas] \ displaystyle = \ binom {k + 1} {0} + \ underbrace {\ binom {k} {0} + \ binom {k} {1}} _ {= \ binom {k + 1} {1 }} + \ underbrace {\ binom {k} {1} + \ binom {k} {2}} _ {= \ binom {k + 1} {2}} + \ cdots + \ underbrace {\ binom {k} { k-1} + \ binom {k} {k}} _ {= \ binom {k + 1} {k}} + \ binom {k + 1} {k + 1} \ tag * {} [/ matemáticas]

[matemáticas] \ displaystyle [\ space \ porque \ space \ text {regla de Pascal} \ space] \ tag * {} [/ math]

[matemáticas] \ displaystyle = \ underbrace {\ binom {k} {0}} _ {= \ binom {k + 1} {0}} + \ binom {k} {0} + \ binom {k} {1} + \ binom {k} {1} + \ binom {k} {2} + \ binom {k} {2} + \ cdots + \ binom {k} {k-1} + \ binom {k} {k-1 } + \ binom {k} {k} + \ underbrace {\ binom {k} {k}} _ {= \ binom {k + 1} {k + 1}} \ tag * {} [/ math]

[matemáticas] \ displaystyle [\ espacio \ porque \ texto {identidades triviales} \ espacio] \ etiqueta * {} [/ matemáticas]

[matemáticas] \ displaystyle = \ Bigg (\ binom {k} {0} + \ binom {k} {1} + \ binom {k} {2} + \ cdots + \ binom {k} {k-1} + \ binom {k} {k} \ Bigg) + \ Bigg (\ binom {k} {0} + \ binom {k} {1} + \ binom {k} {2} + \ cdots + \ binom {k} {k-1} + \ binom {k} {k} \ Bigg) \ tag * {} [/ math]

[matemáticas] \ displaystyle = \ left (2 ^ k \ right) + \ left (2 ^ k \ right) \ tag * {} [/ math]

[matemáticas] \ displaystyle [\ space \ porque \ text {la suposición de} n = k \ space] \ tag * {} [/ math]

[matemáticas] \ displaystyle = 2 \ veces 2 ^ k \ etiqueta * {} [/ matemáticas]

[matemáticas] \ displaystyle = 2 ^ {k + 1} = \ text {RHS} \ tag * {} [/ matemáticas]

[matemática] \ grande {\ porque} [/ matemática] la ecuación es verdadera para [matemática] n = k + 1 [/ matemática] también,

[matemática] \ grande {\ por lo tanto} [/ matemática] por el principio de inducción matemática,

[matemáticas] \ displaystyle \ binom {n} {0} + \ binom {n} {1} + \ binom {n} {2} + \ cdots + \ binom {n} {n-1} + \ binom {n } {n} = 2 ^ n [/ math] es verdadero. ☯

Answer 2

Todas las otras respuestas (hasta ahora) presentan pruebas bastante técnicas, que pueden ser confusas para alguien que no está acostumbrado a leer pruebas matemáticas.

Recuerde que [math] \ displaystyle \ binom {n} {0} [/ math] nos da la cantidad de formas en que podemos seleccionar elementos [math] 0 [/ math] de un conjunto de elementos [math] n [/ math] . Del mismo modo, [math] \ displaystyle \ binom {n} {1} [/ math] es la cantidad de formas en que podemos seleccionar el elemento [math] 1 [/ math] de un conjunto de elementos [math] n [/ math].

En general, para [matemática] k \ en [0, n] [/ matemática], [matemática] \ displaystyle \ binom {n} {k} [/ matemática] es la cantidad de formas en que podemos seleccionar [matemática] k [ / math] elementos de un conjunto de [math] n [/ math] elementos.

Por lo tanto, la suma [matemáticas] \ displaystyle \ binom {n} {0} + \ binom {n} {1} + \ cdots + \ binom {n} {n-1} + \ binom {n} {n} [ /matemáticas]

Nos dice de cuántas maneras en total, podemos elegir cualquier número de elementos de un conjunto de elementos [matemáticos] n [/ matemáticos]

Otra forma de verlo es la siguiente.

Supongamos que debo asignar un índice distinto a cada elemento en el conjunto de elementos [matemáticos] n [/ matemáticos].

Cada elemento en el índice [matemáticas] 1,2, …, n [/ matemáticas] tiene dos estados posibles, ya sea que se elijan o no.

Por lo tanto, el número total de estados es [matemática] 2 \ veces 2 \ veces… \ veces 2 = 2 ^ n [/ matemática]

Completando así la prueba de que [matemáticas] \ displaystyle \ binom {n} {0} + \ binom {n} {1} + \ cdots + \ binom {n} {n-1} + \ binom {n} {n} = 2 ^ n [/ matemáticas]

Answer 3

Es una consecuencia directa del teorema binomial:

[matemáticas] (x + y) ^ n = {n \ elegir 0} x ^ ny ^ 0 + {n \ elegir 1} x ^ {n-1} y ^ 1 + \ cdots + {n \ elegir n} x ^ 0 y ^ n [/ matemáticas]

Tomar [matemáticas] x = y = 1 [/ matemáticas] da

[matemáticas] 2 ^ n = {n \ elige 0} + {n \ elige 1} + \ cdots + {n \ elige n} [/ matemáticas]

Answer 4

Puede pensar en [matemáticas] \ displaystyle \ sum_ {k = 0} ^ {n} \ binom {n} {k} [/ matemáticas] como el número total de formas de elegir subconjuntos de alguna llamada establecida [matemáticas] S [ / matemáticas] tal que [matemáticas] | S | = n [/ matemáticas].

Por lo tanto, puede elegir claramente algunos números de elementos de este conjunto de elementos [math] n [/ math] de muchas maneras diferentes, lo dividiremos en formas de no elegir elementos, formas de elegir el elemento [math] 1 [/ math] y así sucesivamente hasta elegir elementos [math] n [/ math]. Luego sumamos estos para obtener el número total de subconjuntos de [matemáticas] S [/ matemáticas] que podemos falsificar. Esta operación se parece mucho a la suma anterior porque estamos eligiendo elementos [math] 0 [/ math] a [math] n [/ math] de un conjunto de elementos [math] n [/ math] [math] S [/ math]. Por lo tanto, [math] \ displaystyle \ sum_ {k = 0} ^ {n} \ binom {n} {k} [/ math].

Ahora que sabemos que estas dos cosas son equivalentes, pensemos en otra forma de contar cuántos subconjuntos podemos hacer de un conjunto de elementos [math] n [/ math].

[matemáticas] S = [/ matemáticas] {[matemáticas] a_1, a_2, a_3, \ ldots, a_ {n-1}, a_n [/ matemáticas]}

Ahora para cada elemento en [math] S [/ math] podemos elegir tomar ese elemento en nuestro subconjunto, o podríamos elegir no hacerlo. Por lo tanto, existen [math] 2 [/ math] posibilidades para cada elemento en [math] S [/ math] al crear un nuevo subconjunto, ya sea en el subconjunto o no.

Entonces, podemos escribir el número de subconjuntos posibles de [matemática] S [/ matemática] como [matemática] 2 ^ {| S |} = 2 ^ n [/ matemática]

Ahora, con estas dos formas diferentes de contar el número de subconjuntos del mismo conjunto, también deben ser equivalentes. Por lo tanto,

[matemáticas] \ displaystyle \ sum_ {k = 0} ^ {n} \ binom {n} {k} = 2 ^ n [/ matemáticas]

Answer 5

Además de estas excelentes respuestas, también es bueno observar que LHS es una suma de elementos en [matemática] enésima [/ matemática] fila del triángulo de Pascal.

Y sabes que cada elemento en la siguiente fila es una suma de dos elementos encima de él. Por lo tanto, la suma de todos los elementos en la fila inferior es dos veces mayor que en la fila superior.

Luego tiene en cuenta que la fila [matemática] 0th [/ matemática] tiene suma [matemática] 1 = 2 ^ 0 [/ matemática] y cada otra fila tiene una suma dos veces mayor que la anterior. Entonces, la fila [matemática] nth [/ math] tiene una suma de [math] 2 ^ n [/ math].

Answer 6

Considere la expansión binomial:

[matemáticas] \ large \ displaystyle (1 + x) ^ n = \ large \ displaystyle {n \ elegir 0} x ^ 0 + {n \ elegir 1} x ^ 1 + {n \ elegir 2} x ^ 2 +… . {n \ elegir n} x ^ n [/ matemáticas]

Poner [math] \ large \ displaystyle x = 1 [/ math]

[matemáticas] \ implica \ large \ displaystyle (1 + 1) ^ n = \ large \ displaystyle {n \ elige 0} + {n \ elige 1} + {n \ elige 2} +…. {n \ elige n} [/matemáticas]

[matemáticas] \ implica \ large \ displaystyle \ boxed {(2) ^ n = \ large \ displaystyle {n \ elegir 0} + {n \ elegir 1} + {n \ elegir 2} +…. {n \ elegir n }}[/matemáticas]

[matemáticas] \ blacksquare [/ matemáticas]

Answer 7

Expandir (1 + 1) ^ n.