¿Por qué $\sum\limits_{i=0}^k {k\choose i}=2^k$

Question

Posible duplicado:
Demostración de un caso especial del teorema del binomio

¿Puede alguien explicarme por qué

$$\sum\limits_{i=0}^k {k\choose i}=2^k\,?$$

Gracias de antemano

Answer 1

Interpretación combinatoria obligatoria: el número de formas de elegir un subconjunto de $\{1,2,,\dots,k\}$ es igual al número de formas de hacer una elección de $i$ está en el subconjunto para $i=1,2,\dots,k$ de forma independiente, que es $2^k$ (algo así como tener $k$ interruptores numerados de encendido/apagado todos en una fila, donde "encendido" significa que el número del interruptor se pone en el subconjunto). Alternativamente, es el número de formas de elegir $0$ elementos fuera, además del número de formas de elegir $1$ elementos fuera, además del número de formas de elegir $2$ elementos fuera, $\dots$ más el número de formas de elegir todas $k$ elementos fuera, que es $\sum_{i=0}^k{k\choose i}$ .

Answer 2

Creo que la forma habitual de explicarlo es utilizar Fórmula binomial de Newton es decir $$ (a+b)^k = \sum\limits_{i=0}^k {k\choose i}a^ib^{k-i} $$ entonces pon $a=b=1$ , por lo que tiene $2^k$ en el lado izquierdo y la suma que te interesa en el lado derecho.

La fórmula del Binomio la puedes demostrar fácilmente por inducción - pero creo que para tu ejemplo si no conoces la fórmula del Binomio, incluso debería ser más fácil demostrar por inducción que $$ \sum\limits_{i=0}^k {k\choose i} = 2^k. $$