¿Cuál es la forma más fácil de probar$\sum \limits_{r=1}^n \binom{2n+1}{r} = 4^n-1$?

Question

Cual es la manera más fácil de probar que $\sum \limits_{i=1}^n \binom{2n+1}{r} = 4^n-1$?

Me encontré con este problema, mientras que la solución de esta pregunta:

Un estudiante podrá seleccionar en la mayoría de las $n$ libros de una colección de $(2n+1)$ libros. Si el número total de libros que puede seleccionar es $63$, entonces, ¿cuál es el valor de $n$?

Evidentemente, este hierve a resolver para $n$ $\sum \limits_{i=1}^n \binom{2n+1}{r} = 63$, he utilizado Mathematica para derivar que cerrar el formulario. Me pregunto cómo podríamos conseguir que sin las ayudas? Agradecería un algebraicas o enfoque combinatorio.

Answer 1

$$ \ binom {2n +1} {r} = \ binom {2n +1} {2n +1-r} $$

Así

$$ \ sum \ limits_ {r = 1} ^ n \ binom {2n +1} {r} = \ sum \ limits_ {r = 1} ^ n \ binom {2n +1} {2n +1-r} = \ sum \ limits_ {s = n +1} ^ {2n} \ binom {2n +1} {s} $$

Por lo tanto

$$ 2 \ sum \ limits_ {r = 1} ^ n \ binom {2n +1} {r} = \ sum \ limits_ {r = 1} ^ n \ binom {2n +1} {r} + \ sum \ limits_ {r = n +1} ^ {2n} \ binom {2n +1} {r} = \ sum \ limits_ {r = 0} ^ {2n +1} \ binom {2n +1} {r} -2 = 2 ^ {2n +1} -2 $$

Answer 2

Un recuento de argumento, que es básicamente una reformulación del enfoque algebraico.

Considerar un subconjunto de a $\{1,2, \dots, 2n+1\}$ que no tiene más de $n$ elementos.

Esto puede ser asignada en un 1-1 de la moda a un conjunto que tiene al menos $n+1$ elementos, tomando el complemento.

Así, el número total de conjuntos de, con no más de $n$ elementos es la mitad del número total de sets, que viene a $\dfrac{2^{2n+1}}{2} = 4^n$.

Puesto que usted no está incluido el conjunto vacío, el total que usted está buscando es $4^n - 1$.

Para un recuento de argumento para contar el número total de subconjuntos:

Ha $2$ opciones para cada elemento, se incluyen en el conjunto de no. Así que el total de número de $2^{2n+1}$.