Evaluar sumas algebraicamente o Combinatorially

Question

Tener en cuenta

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

(2) $$\sum_{k=0}^{n}\binom{n}{k}\frac{k!}{(n+k+1)!}$ $

Estas cantidades parecen demasiado difíciles (en mi mente) evaluar combinatorially. ¿Cuáles son algunos buenos métodos para atacar estos problemas algebraico?

Answer 1

Una combinatoria argumento para (1) no es demasiado duro. Primera reescritura de la suma:

$$\sum_k\binom{n}k2^{k-n}=2^{-n}\sum_k\binom{n}k2^k\;.$$

Ahora $\binom{n}k2^k$ es el número de formas de seleccionar un $k$-subconjunto $S$ $[n]$ y, a continuación, un subconjunto $T$$S$, lo $\sum_k\binom{n}k2^k$ es el número de maneras de dividir $[n]$ en tres subconjuntos. Esto es claramente $3^n$, por lo que la expresión original es $\left(\frac32\right)^n$.

No estoy en el momento de ver un útil combinatoria interpretación de la segunda suma, pero puedo evaluar. Si

$$f(n)=\sum_{k=0}^n\binom{n}k\frac{k!}{(n+k+1)!}\;,$$

a continuación, tenemos los siguientes datos:

$$\begin{array}{c|r} n&f(n)\\ \hline 0&1=\frac{2^0}{1!!}\\ 1&\frac12+\frac16=\frac23=\frac{2^1}{3!!}\\ 2&\frac16+\frac2{24}+\frac2{120}=\frac4{15}=\frac{2^2}{5!!}\\ 3&\frac1{24}+\frac1{40}+\frac1{120}+\frac1{840}=\frac8{105}=\frac{2^3}{7!!}\\ 4&\frac1{120}+\frac1{180}+\frac1{420}+\frac1{1680}+\frac1{15120}=\frac{16}{945}=\frac{2^4}{9!!} \end{array}$$

Aparentemente $f(n)=\dfrac{2^n}{(2n+1)!!}=\dfrac{4^nn!}{(2n+1)!}$. Ahora

$$\begin{align*} \frac{(2n+1)!}{n!}f(n)&=\frac{(2n+1)!}{n!}\sum_{k=0}^n\binom{n}k\frac{k!}{(n+k+1)!}\\\\ &=\frac1{n!}\sum_{k=0}^n\binom{n}kk!(2n+1)^{\underline{n-k}}\\\\ &=\frac1{n!}\sum_{k=0}^nn^\underline k(2n+1)^{\underline{n-k}}\\\\ &=\sum_{k=0}^n\frac{(2n+1)^{\underline{n-k}}}{(n-k)!}\\\\ &=\sum_{k=0}^n\frac{(2n+1)!}{(n-k)!(n+k+1)!}\\\\ &=\sum_{k=0}^n\binom{2n+1}{n-k}\\\\ &=\sum_{k=0}^n\binom{2n+1}k\;. \end{align*}$$

(Aquí se $x^{\underline k}$ es la caída de factorial.) Y

$$\sum_{k=0}^n\binom{2n+1}k=\sum_{k=0}^n\binom{2n+1}{2n+1-k}=\sum_{k=n+1}^{2n+1}\binom{2n+1}k\;,$$

así

$$\frac{(2n+1)!}{n!}f(n)=\frac12\sum_{k=0}^{2n+1}\binom{2n+1}k=2^{2n}=4^n\;,$$

y la conjetura de que $f(n)=\dfrac{2^n}{(2n+1)!!}=\dfrac{4^nn!}{(2n+1)!}$ está establecido.

Answer 2

La segunda suma

$$ \sum_{k=0}^{n} \binom{n}{k} \frac{k!}{(n+k+1)!} $$

puede ser reescrita como

$$\frac{n!}{(2n+1)!} \sum_{k=0}^{n} \binom{2n+1}{n-k} = \frac{2^{2n} n!}{(2n+1)!}$$

expandir $\binom{n}{k} = \frac{n!}{(n-k)!k!}$, anular el $k!$ y multiplicar y dividir por $(2n+1)!$ y

$\sum{k=0}^{n} \binom{2n+1}{n-k} = \binom{2n+1}{n} + \binom{2n+1}{n-1} + \dots + \binom{2n+1}{0} = \frac{1}{2} \sum{k=0}^{2n+1} \binom{2n+1}{k} = 2^{2n}$

Answer 3

ps

Answer 4

$(1)$, Tener en cuenta el teorema del binomio. Primero, escriba $2^{k-n}$ $\left(\frac{1}{2}\right)^{n-k}$. Entonces: $$\sum{k=0}^{n} {n \choose k} 2^{k-n} = \sum{k=0}^{n} {n \choose k} \left(\frac{1}{2}\right)^{n-k} 1^{k} = \left(1+\frac{1}{2}\right)^{n}=\left(\frac{3}{2}\right)^{n}$ $

Numérico los resultados sugieren que la segunda suma puede escribirse como %#% $ #%