Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

Question

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

suma
Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

terraza

Sé cómo probar esta identidad algebraicamente, pero esa es la forma estúpidamente aburrida de hacer problemas. No puedo pensar en una prueba combinatoria para esto, como en el uso de comités de conteo o algo así. Es difícil lidiar con lo negativo. $2$ ...

\sum_{k = 0}^{norte} (\binom{norte}{k}) {(- 2)}^{k} = (- 1)^{norte}

$\displaystyle\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n$

Cualquier ayuda es apreciada, gracias!

hmakholm sobra a Monica

(1 - 2)^{n}

$(1-2)^n$ . Teorema del binomio.

aprendiz

@HenningMakholm, las preguntas solicitan una prueba combinatoria. La demostración algebraica es trivial.

terraza

@HenningMakholm Wow, eso es mucho más fácil de lo que tenía en mente cuando lo demostraba algebraicamente. Odio la inducción (creo que le quita diversión a probar cosas) y lo estaba haciendo por inducción...

Respuestas (1)

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

@HenningMakholm, las preguntas solicitan una prueba combinatoria. La demostración algebraica es trivial.
@HenningMakholm Wow, eso es mucho más fácil de lo que tenía en mente cuando lo demostraba algebraicamente. Odio la inducción (creo que le quita diversión a probar cosas) y lo estaba haciendo por inducción...

Brian M Scott · Answer 1

La prueba combinatoria más natural comienza multiplicando la identidad deseada por $(-1)^n$ para hacerlo

\sum_{k = 0}^{norte} (\binom{norte}{k}) 2^{k} (- 1)^{norte - k} = 1 .

$\sum_{k=0}^n\binom{n}k2^k(-1)^{n-k}=1\;.$

Por supuesto, esto es inmediato del teorema del binomio, pero si desea algo más explícitamente combinatorio, puede reemplazar $k$ por $n-k$ Llegar

\sum_{k = 0}^{norte} (\binom{norte}{k}) (- 1)^{k} 2^{norte - k} = 1 .

$\sum_{k=0}^n\binom{n}k(-1)^k2^{n-k}=1\;.$

Supongamos que queremos contar los subconjuntos de $[n]=\{1,\ldots,n\}$ que no contienen ningún elemento de $[n]$ . Por supuesto, el único subconjunto de este tipo es $\varnothing$ , por lo que el valor debe ser $1$ . Por otro lado, si por $k\in[n]$ dejamos $\mathscr{A}_k$ Sea la familia de subconjuntos de $[n]$ que contiene $k$ , entonces para cualquier no vacío $F\subseteq[n]$ tenemos

| ⋂_{k \in F} A_{k} | = 2^{norte - k},

$\left|\bigcap_{k\in F}\mathscr{A}_k\right|=2^{n-k}\;,$

y aquí están $\binom{n}k$ semejante $F\subseteq[n]$ , por lo que el resultado se sigue del principio de inclusión-exclusión .

¡Gracias por un enfoque muy bueno para el problema! Tal vez la forma algebraica sea más fácil después de todo: lo estaba haciendo por inducción, lo que me parece extremadamente aburrido / poco interesante como técnica de prueba, no me di cuenta de que era posible simplemente expandir $(1-2)^n$ como señaló Henning Makholm.

Prueba combinatoria para la identidad ∑nk=0(nk)(−2)k=(−1)n∑k=0n(nk)(−2)k=(−1)n\sum_{k=0}^n \binom{n}{k}\left(-2\right)^k = (-1)^n

terraza

hmakholm sobra a Monica

aprendiz

terraza

Respuestas (1)

Brian M Scott

terraza

Brian M Scott

Prueba combinatoria de la identidad 3n=∑nk=0(nk)2k3n=∑k=0n(nk)2k3^n=\sum_{k=0}^n \binom nk 2^k

Verificación de la solución: Demuestre que ∑ni=0(n+an−i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)∑i=0n(n+an− i)(i+a+1i)=2n(n+aa)+2n−1(n+aa+1)\sum_{i=0}^{n}{\binom{n+a}{ni}\ binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1} para n ≥1n≥1n\geq 1

Prueba combinatoria de ∑k=0n(nk)3k=4n∑k=0n(nk)3k=4n\sum\limits_{k=0}^n {n \choose k}3^k=4^n

Interpretación combinatoria para la identidad ∑i(mi)(nj−i)=(m+nj)∑i(mi)(nj−i)=(m+nj)\sum\limits_i\binom{m}{i}\ binom{n}{ji}=\binom{m+n}{j}?

Demuestra que para r,n∈Nr,n∈Nr,n \in \mathbb{N} con r≥nr≥nr \geq n, ∑n−1i=0(−1)i(ni)(r+n− i−1r)=(r−1n−1)∑i=0n−1(−1)i(ni)(r+n−i−1r)=(r−1n−1)\sum_{i=0} ^{n-1} (-1)^i \binom{n}{i} \binom{r+ni-1}{r} = \binom{r-1}{n-1}

Simplificando el producto de múltiples expansiones binomiales

Pregunta de prueba de suma binomial/combinatoria

Suma del producto de coeficientes binomiales: ∑nk=0(−1)k(nk)(n+kk)=(−1)n∑k=0n(−1)k(nk)(n+kk)=(− 1)n\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{n + k}{k} = (-1)^n

Prueba combinatoria sobre factoriales decrecientes y sumas de factoriales decrecientes

Prueba combinatoria para series de números de Stirling y coeficientes binomiales