Prueba algebraica que $\sum\limits_{i=0}^n \binom{n}{i}=2^n$

Question

Soy muy consciente de la combinatoria de la variante de la prueba, es decir, observando que cada fórmula es una representación diferente para el número de subconjuntos de un conjunto de $n$ elementos. Tengo curiosidad por ver si hay una serie de manipulaciones algebraicas que pueden llevar de$\sum\limits_{i=0}^n \binom{n}{i}$$2^n$.

Answer 1

Aquí tienes uno. Deje $g(n) = \sum \limits_{i=0}^n \binom{n}{i}$. Entonces

$$g(n+1) - g(n) = \sum_{i=0}^{n+1} \binom{n+1}{i} - \sum_{i=0}^n \binom{n}{i} = \sum_{i=0}^{n+1} \left(\binom{n+1}{i} - \binom{n}{i}\right) = \sum_{i=0}^{n+1} \binom{n}{i-1} $$ $$= \sum_{i=0}^n \binom{n}{i} = g(n).$$ Aquí, utilizamos el hecho de que $\binom{n}{n+1} = \binom{n}{-1} = 0$, así como el binomio de recurrencia $\binom{n+1}{i} = \binom{n}{i} + \binom{n}{i-1}$.

Así tenemos a $g(n+1) = 2g(n)$,$g(0) = 1$. Desde $g(n)$ se duplica cada vez que $n$ se incrementa en 1, debemos tener $$g(n) = \sum_{i=0}^n \binom{n}{i} = 2^n.$$

Answer 2

Simplemente use la fórmula binominal.

$$(a + b)^n = \sum_{k=0}^n {n \choose k} a^k b^{n - k}$$

Con $a = b = 1$ tiene su resultado.

Answer 3

Bueno, aquí hay uno.

$$\sum_{i=0}^n \binom{n}{i}=2^n$$ $$\sum_{i=0}^n \binom{n}{i}+\sum_{i=0}^n \binom{n}{i}=2^{n+1}$$ $$\binom{n}{0}+\left [ \binom{n}{0}+\binom{n}{1} \right ]+...+\left [ \binom{n}{n-1}+\binom{n}{n}\right ]+\binom{n}{n}=2^{n+1}$$ $$\sum_{i=0}^{n+1} \binom{n+1}{i}=2^{n+1}$$

Answer 4

Usted podría utilizar exponencial funciones de generación de demostrar esta identidad. $$\begin{eqnarray}\sum_{n\ge0}2^n\frac{x^n}{n!}&=&\sum_{n\ge0}\frac{(2x)^n}{n!}\\&=&e^{2x}\\&=&e^xe^x\\&=&\sum_{i\ge0}\frac{x^i}{i!}\sum_{j\ge0}\frac{x^j}{j!}\\&=&\sum_{n\ge0}\sum_{i=0}^{n}\frac{x^i}{i!}\frac{x^{n-i}}{(n-i)!}\\&=&\sum_{n\ge0}\sum_{i=0}^n\binom{n}{i}\frac{x^n}{n!}\end{eqnarray} $$ Ahora, la comparación de los coeficientes de $x^n$ ${n\ge0}$ da la identidad.