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

Question

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

suma
Matemáticas
combinatoria
pruebas combinatorias
coeficientes binomiales

miguels

Usando la siguiente ecuación:

\sum_{k = 0}^{norte} (\binom{norte}{k}) 3^{k} = 4^{norte}

$\sum_{k=0}^n {n \choose k}3^k=4^n$

Necesito demostrar que ambos lados de la ecuación resuelven el mismo problema combinatorio.

Es fácil ver que el lado derecho de la ecuación cuenta el número de formas de dividir $n$ diferentes bolas en $4$ baldes

¿Es correcto decir que el lado izquierdo de la ecuación resuelve el mismo problema de la siguiente manera (?):

Desde $\sum\limits_{k=0}^n {n \choose k} 3^k= \sum\limits_{k=0}^n {n \choose n-k}3^k$ , podemos cambiar la ecuación a:

\sum_{k = 0}^{norte} (\binom{norte}{norte - k}) 3^{k} = 4^{norte}

$\sum_{k=0}^n {n \choose n-k}3^k=4^n$

Y a partir de la nueva ecuación, es más fácil ver que cada coeficiente binomial elige el número de bolas para poner en el primer balde, y $3^k$ divide el resto $k$ bolas entre el resto 3 baldes sin limite.

izq.

Supongo que no quieres esto:

\sum_{k = 1}^{n} (\binom{n}{k}) 3^{k} = \sum_{k = 1}^{n} (\binom{n}{k}) 1^{n - k} 3^{k} = (1 + 3)^{n} = 4^{n}

$\sum_{k=1}^n {n \choose k}3^k= \sum_{k=1}^n {n \choose k} 1^{n-k} 3^k=(1+3)^n = 4^n$ ...

miguels

Gracias @lhf, pero no, solo estoy buscando una explicación combinatoria.

cristian blatter

@MichaelS: Su argumento combinatorio es simple y correcto.

Dilip sarwate

¿Es correcto el resultado que MichaelS intenta probar? entiendo eso si

n = 1

$n = 1$ , entonces

\sum_{k = 1}^{1} (\binom{1}{k}) 3^{k} = (\binom{1}{1}) 3^{1} = 3 = 4^{1} = 4

$\sum_{k=1}^{1}\binom{1}{k}3^k = \binom{1}{1}3^1 = 3 = 4^1 = 4$ ? El teorema del binomio dice que

4^{n} = (3 + 1)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) 3^{k} 1^{n - k} = \sum_{k = 0}^{n} (\binom{n}{k}) 3^{k}

$4^n = (3+1)^n = \sum_{k=0}^n \binom{n}{k} 3^k1^{n-k} = \sum_{k=0}^n \binom{n}{k} 3^k$ que es un resultado ligeramente diferente (tenga en cuenta el diferente rango de suma).

miguels

@ChristianBlatter, ¡Gracias! Feliz de ver que lo hice bien..

miguels

@DilipSarwate, escribí k=1 en lugar de k=0, lo arreglaré de inmediato.

André Nicolás

Todo esta bien. Para mí, prefiero contar las palabras de longitud

n

$n$ sobre el alfabeto

{1, 2, 3, 4}

$\{1,2,3,4\}$ . Mismo análisis.

Respuestas (2)

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

Supongo que no quieres esto: $\sum_{k=1}^n {n \choose k}3^k= \sum_{k=1}^n {n \choose k} 1^{n-k} 3^k=(1+3)^n = 4^n$ ...
Gracias @lhf, pero no, solo estoy buscando una explicación combinatoria.
¿Es correcto el resultado que MichaelS intenta probar? entiendo eso si $n = 1$ , entonces $\sum_{k=1}^{1}\binom{1}{k}3^k = \binom{1}{1}3^1 = 3 = 4^1 = 4$ ? El teorema del binomio dice que $4^n = (3+1)^n = \sum_{k=0}^n \binom{n}{k} 3^k1^{n-k} = \sum_{k=0}^n \binom{n}{k} 3^k$ que es un resultado ligeramente diferente (tenga en cuenta el diferente rango de suma).
@ChristianBlatter, ¡Gracias! Feliz de ver que lo hice bien..
@DilipSarwate, escribí k=1 en lugar de k=0, lo arreglaré de inmediato.
Todo esta bien. Para mí, prefiero contar las palabras de longitud $n$ sobre el alfabeto $\{1,2,3,4\}$ . Mismo análisis.

Immanuel Weihnachten · Answer 1

Sí, estoy de acuerdo con tu interpretación del lado izquierdo, y también el comentario de lhf se puede ver de la misma manera:

$4^n$ las formas de dividir $n$ bolas en $4$ cajas
$(3+1)^n$ lo mismo de arriba
$\sum_{k=0}^n {n \choose k} 1^{n-k} 3^k$ para cada $k$ , las formas de elegir $k$ pelotas entre los $n$ bolas que tienes, veces las formas de poner $n-k$ bolas en una caja, veces las formas de poner el resto $k$ bolas en el resto $3$ cajas
$\sum_{k=0}^n {n \choose k}3^k$ como arriba, usando $1^{n-k}=1$

El resultado que está tratando de probar no es correcto y la interpretación que da es defectuosa.
Emanuele, escribí en la pregunta k = 1 en lugar de k = 0, edite su respuesta para que la prueba no sea incorrecta. Ya he editado la pregunta a k=0.
Lo siento. Simplemente copié la identidad de lhf porque era demasiado perezoso, no noté esos errores tipográficos. Supongo que @Dilip se refería a eso.

qwr · Answer 2

El RHS se parece a la fórmula para el número de cuerdas de base 4. Entonces, también podemos interpretar el LHS de manera similar al conteo de bolas como el conteo de todas las posibles cadenas de base 3 que se pueden colocar en el $n$ cadena de longitud y llenando el resto con el dígito restante.

Por ejemplo

X X X 012201 X X 021 X X

$XXX012201XX021XX$ dónde

(\binom{n}{k})

$\binom n k$ elige donde

0, 1, 2

$0,1,2$ ir y

3^{k}

$3^k$ cuenta todas las cadenas posibles.

Debe tener cuidado al especificar cubos, ya que son distintos , lo que queda claro a partir del orden de una cadena.

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

miguels

izq.

miguels

cristian blatter

Dilip sarwate

miguels

miguels

André Nicolás

Respuestas (2)

Immanuel Weihnachten

miguels

Dilip sarwate

miguels

Immanuel Weihnachten

qwr

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

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

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

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