Verificación de prueba$\sum_{k=0}^n \binom{n}{k} = 2^n$ (cálculo de Spivak)

Question

$$\sum_{k=0}^n \binom{n}{k} = 2^n$ $ , Voy a utilizar la inducción para resolver probar esto. Entonces

$$\sum_{k=0}^n \binom{n}{k} = 2^n = \binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n - 1} + \binom{n}{n}$$

Primera prueba con n = 1

$$\binom{1}{0} + \binom{1}{1} = 2^1$$

Desde $$\binom{1}{0} = \binom{1}{1} = 1$$

es cierto.

Ahora supongamos que es cierto con $n$ si es cierto con $n + 1$

A continuación, multiplique ambos lados por dos

$$2(2^n) = 2(\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n - 1} + \binom{n}{n})$$

$$2^{n+1} = 2\binom{n}{0} + 2\binom{n}{1} + ... + 2\binom{n}{n - 1} + 2\binom{n}{n}$$

$$2\binom{n}{0} + 2\binom{n}{1} + ... + 2\binom{n}{n - 1} + 2\binom{n}{n} = \binom{n}{0} + \binom{n}{0} + \binom{n}{1} + \binom{n}{1} + ... + \binom{n}{n} + \binom{n}{n} $$

El primer término tiene dos igual término, entonces, se suma el último con el primero del siguiente plazo, y obtendrás esto

$$\binom{n}{0} + \binom{n}{1} +... + \binom{n}{n-1} + \binom{n}{n}$$

Si usamos esta ecuación (Ya probado)

$$\binom{n}{k-1} + \binom{n}{k} = \binom{n+1}{k} $$

Por supuesto, vamos a tener dos plazo sin que se suma, una $\binom{n}{0}$ $\binom{n}{n}$

Podemos escribir estos dos periodos como este

$$\binom{n}{0} = \binom{n}{n} = \binom{n+1}{0} = \binom{n+1}{n+1}$$

Entonces, tenemos

$$2^{n+1} = \binom{n+1}{0} + \binom{n+1}{1} + ... + \binom {n+1}{n+1}$$

Y ya se demostró. Nota: Sólo si tomamos $0! = 1$

Tengo que probar estas demasiado.

$\sum_{k}^n \binom{n}{m} = 2^{n-1}$ Si $m$ es incluso. Y $\sum_{j}^n \binom{n}{j} = 2^{n-1}$ Si $j$ es impar. Entonces, sólo me dijo que

Si $$\sum_{m}^n \binom{n}{m} + \sum_{j}^n \binom{n}{j} = \sum_{k=0}^n \binom{n}{k} $$

Entonces

$$2^{n - 1} + 2^{n - 1} = 2^n$$

Lo cual es cierto, entonces, yo ya lo demuestran. Y tengo una pasada.

$$\sum_{i=0}^n (-1)^i\binom{n}{i} = 0$$

si n es impar. Entonces

$$\binom{n}{0} - \binom{n}{1} + ... + \binom{n}{n-1} - \binom{n}{n} = 0$$

Y eso se puede resolver saber que $$\binom{n}{k} = \binom{n}{n - k}$$

Y si n es incluso

$$\binom{n}{0} - \binom{n}{1} + ... - \binom{n}{n-1} + \binom{n}{n} = 0$$

Eso significa que cada término negativo si cuando n es impar, entonces, podemos usar los dos últimos probar a probarlo

Si $$\sum_{m}^n \binom{n}{m} - \sum_{j}^n \binom{n}{j} = 0$$

Entonces

$$2^{n-1} - 2^{n-1} = 0$$

Lo cual es cierto.

Y eso es todo, quiero saber si mi prueba están muy bien y son rigurosos y ¿cuál es el significado de cada una de las combinaciones que probar .

Quiero saber demasiado acerca mejor a probar estos (O de las formas más intuitivo)

Answer 1

aquí es otro enfoque:

Considere un conjunto con $n$ objetos. Hay $\binom nk$ formas de elegir los $k$ de ellos. De que manera te $\sum_{i=0}^n\binom ni$ formas de elegir los objetos del conjunto. Por otro lado, tenemos la opción de elegir cada elemento o no.Que da $2^n$. Y, por supuesto, son iguales, ya que ambos representan el número de formas de elegir algunos de los objetos del conjunto.

El segundo y el tercero son en realidad la misma (se puede ver por qué?). Utilizando el triángulo de Pascal $\sum_{2|i}^n\binom ni=\sum_{2\nmid i}^n\binom ni$, ya que ambos igual a la suma de la línea por encima de ellos. (que es $2^{n-1}).$

Answer 2

Un matemático mejor que usted o una vez luchó tan poderosamente con esta pregunta, y le dije a ampliar $(1+1)^n$ con la expansión binomial.

Answer 3

Estos son corolarios del Teorema del Binomio, que establece que $$(x + y)^n = \sum_{k = 0}^{n} \binom{n}{k} x^{n - k}y^k$$

Si establecemos $x = y = 1$, obtenemos $$2^n = (1 + 1)^n = \sum_{k = 0}^{n} 1^{n - k}1^k = \sum_{k = 0}^{n} \binom{n}{k}$$ lo que significa que el número de subconjuntos de un conjunto con $n$ elementos es $2^n$.

Si establecemos $x = 1$$y = -1$, obtenemos $$0^n = [1 + (-1)]^n = \sum_{k = 0}^{n} 1^{n - k}(-1)^{k} = \sum_{k = 0}^{n} (-1)^k\binom{n}{k}$$ Observe que cada término en que $k$ es positivo y cada término en que $k$ es impar es negativo. Por lo tanto, $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} - \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = 0 \tag{1}$$ lo que significa que el número de subconjuntos con un número par de elementos es igual al número de subconjuntos con un número impar de elementos.

Ya que cada subconjunto tiene un número par de elementos o de un número impar de elementos, $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} + \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = \sum_{k = 0}^{n} \binom{n}{k} = 2^n \tag{2}$$ La adición de las ecuaciones 1 y 2 de los rendimientos $$2\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^n \implies \sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k} = 2^{n - 1}$$ lo que significa que el número de subconjuntos con un número de subconjuntos de a $2^{n - 1}$.

Dado que el número de subconjuntos con un número impar de elementos es igual al número de subconjuntos con un número par de elementos, el número de subconjuntos con un número impar de elementos es $$\sum_{k = 0}^{\lfloor \frac{n}{2} \rfloor} \binom{n}{2k + 1} = 2^{n - 1}$$