Demostrar por inducción que $ \sum_{k=0}^n{n \choose k} = 2^n$

Question

Demostrar por inducción que para todo $n \ge 0$:

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

En el paso inductivo, uso de identidad de Pascal, que es:

$${n+1 \choose k} = {n \choose k-1} + {n \choose k}.$$

Sólo puedo demostrar usando el teorema del binomio, no inducción.

Answer 1

Para basic paso n = 0:
$\binom{0}{0}=\frac{0!}{0!0!}=2^0$

Para el paso de inducción:
Sea k un número entero tal que $0\lt{k}$ y para todos L, $0\le{L}\le{k}$ donde $L\in{I}$, la fórmula soporte de verdad.
A continuación:
$$\binom{k}{0}+\binom{k}{1}+...+\binom{k}{k}=2^k$$
Ahora como puede ser ilustrado fácilmente $\binom{k}{0}=\binom{k+1}{0}$ y $\binom{k}{k}=\binom{k+1}{k+1}$.
Ahora mediante el uso de identidad de Pascal,
También es cierto $$\begin{align}\binom{k+1}{0}+\binom{k+1}{1}+\binom{k+1}{2}+...+\binom{k+1}{k}+\binom{k+1}{k+1}\=\binom{k+1}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k+1}{k+1}\=\binom{k}{0}+\binom{k}{0}+\binom{k}{1}+\binom{k}{1}+\binom{k}{2}+...+\binom{k}{k-1}+\binom{k}{k}+\binom{k}{k}\=2{\sum_{i=0}^k\binom{k}{i}}\=22^k\=2^{k+1}\end{align}$ por lo tanto, por el segundo principio de inducción finita esta fórmula es válida para todos números enteros greator que o igual a $k+1$ %#% $ #% como la fórmula.

Answer 2

Bueno, aquí está: \sum{k=0}^{n+1 $$} {n +1\choose k} = {n +1\choose 0} + {n +1\choose 1} + \ldots + {n +1\choose n} + {n +1\choose n +1} $$ $$ = 1 + {n\choose 0} + {n\choose 1} + {n\choose 1} + {n\choose 2} + \ldots + {n\choose n-1} + {n n\choose} + 1 $$ $$ = {n\choose 0} + {n\choose 0} + {n\choose 1} + {n\choose 1} + \ldots + {n\choose n-1} + {n\choose n-1} + {n n\choose} + {n\choose n} $$ $$ = \times \sum{k=0}^n 2 {n\choose k} $$ ahora inducir!