simplificar la suma del factorial (paseo aleatorio)

Question

Sospecho que la expresión

$$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$

se simplifica a

$$\frac{2^N}{(N-1)!}$$

Pero no encuentro los pasos intermedios. ¿Puede alguien darme una pista de cómo puedo deducir este resultado?

(La expresión surge al calcular la posición final media tras un paseo aleatorio de $N$ pasos).

Answer 1

Tienes razón. Multiplicando ambos lados por $N!$ se obtiene: $$\sum_{n=0}^{N} (N-2n)^2 \binom{N}{n} = N2^{N}$$

3 Lemas, basados en $\binom{n}{k}=\frac{n}{k} \binom{n-1}{k-1}$ (nótese que en cada lema aplico los lemas anteriores):

1. $\sum_{n=0}^{N}\binom{N}{n} = 2^{N}$

2. $\sum_{n=0}^{N} n\binom{N}{n} = N\sum_{n=1}^{N} \binom{N-1}{n-1} = N2^{N-1}$

3. $\sum_{n=0}^{N} n^2\binom{N}{n} = N\sum_{n=1}^{N} n\binom{N-1}{n-1} = N(\sum_{n=1}^{N} (n-1)\binom{N-1}{n-1} + \sum_{n=1}^{N} \binom{N-1}{n-1})=N((N-1)2^{N-2} + 2^{N-1})$

Así que ahora sólo es cuestión de ampliar la suma original: $$\sum_{n=0}^{N} (N-2n)^2 \binom{N}{n} = N^2 \sum_{n=0}^{N}\binom{N}{n} - 4N \sum_{n=0}^{N} n \binom{N}{n} +4 \sum_{n=0}^{N} n^2\binom{N}{n} = N^2 2^N -4N^{2}2^{N-1}+4N((N-1)2^{N-2}+2^{N-1})=N2^{N}$$

EDITAR: Como veo este tipo de preguntas con mucha frecuencia, voy a presentar una guía sobre cómo simplificar $\sum_{k=0}^{n} P(n,k)\binom{n}{k}$ para cualquier polinomio $P$ En su caso $(n-2k)^2$ .

Paso 1: Reducir para calcular $\sum_{k=0}^{n} k^i \binom{n}{k}$ calculando la suma original en forma de monomio.

Paso 2: Observe que $$\sum_{k=0}^{n} \binom{k}{i} \binom{n}{k} = \binom{n}{i} 2^{n-i}$$ Esta identidad generaliza mi lema. Se puede demostrar de muchas maneras:

• Por inducción en $i$ (como en los lemas, utilice $\binom{k}{i} \binom{n}{k} = \binom{k-1}{i-1} \binom{n-1}{k-1}\frac{n}{i}$ )
• Al diferenciar la identidad $\sum_{k=0}^{n} \binom{n}{k} x^k = (1+x)^n$ $i$ veces, dividiendo por $i!$ y el enchufe $x=1$ .
• También hay una prueba combinatoria (LHS cuenta maneras de elegir un subconjunto especial de $i$ personas fuera de $n$ y luego elegir un conjunto que los contenga, de tamaño $k$ , ya que $k$ corre de $0$ a $n$ ).
• Una breve prueba directa: $\binom{k}{i} \binom{n}{k} = \binom{n}{i}\binom{n-i}{n-k}$ .

Paso 3: Escribir $k^i$ como una combinación de $\binom{k}{j}$ para $j\le i$ y aplicar el paso 2. No te preocupes, hay un atajo como siempre: $$k^i = \sum_{j=0}^{i} c_{i,j} \binom{k}{j}$$ $$c_{i,j} = \# \{ \text{surjective functions from i-set to j-set} \}$$ Esto también tiene pruebas algebraicas y combinatorias.

• Lo algebraico va en la línea de calcular el $j$ derivada discreta de $f(k)=k^i$ en $0$ , obteniendo $c_{i,j}$ y descifrar lo que cuenta (es igual a la suma $\sum_{t=0}^{j} t^i(-1)^{t-j} \binom{j}{t}$ - ¿Inclusión-exclusión alguien?).
• Pero la combinatoria es más fría - nota que $k^i$ cuenta el número de funciones de un $i$ -se ajusta a un $k$ -set, y luego entender el RHS.

Conclusión: siempre obtendrá la simplificación $2^n Q(n)$ , donde $Q$ es un polinomio que depende linealmente de $P(n,k)$ .

Me encanta la interacción entre las soluciones algebraicas y combinatorias...

Answer 2

$$(N-2n)^2 = (N-n)^2 + n^2 - 2n(N-n)$$ Por lo tanto, \begin{align} S_N(n) & = \dfrac{(N-2n)^2}{n!(N-n)!}\\ & = \dfrac{(N-n)^2 + n^2 - 2n(N-n)}{n!(N-n)!}\\ & = \dfrac{N-n}{n!(N-n-1)!} + \dfrac{n}{(n-1)! (N-n)!} - 2 \dfrac1{(n-1)!(N-n-1)!}\\ & = \dfrac1{n!(N-n-2)!} + \dfrac1{n!(N-n-1)!} + \dfrac1{(n-2)!(N-n)!} + \dfrac1{(n-1)!(N-n)!} - \dfrac2{(n-1)!(N-n-1)!} \end{align} Ahora, observe que a partir de la expansión binomial de $2^{N-k-m}$ tenemos que $$\sum_{n=\min(k,a)}^{\max(N-m,b)} \dfrac1{(n-k)!(N-n-m)!} = \dfrac{2^{N-k-m}}{(N-k-m)!}$$ Por lo tanto, $$\sum_{n=0}^{n=N} S_N(n) = \dfrac{2^{N-2}}{(N-2)!} + \dfrac{2^{N-1}}{(N-1)!} + \dfrac{2^{N-2}}{(N-2)!} + \dfrac{2^{N-1}}{(N-1)!} -2 \dfrac{2^{N-2}}{(N-2)!} = \dfrac{2^N}{(N-1)!}$$

Answer 3

Tenga en cuenta que $\sum_{n=0}^{N}\frac{x^{2n}}{n!(N-n)!}=\frac{(1+x^2)^N}{N!}$ . Así: $$\sum_{n=0}^{N}\frac{x^{2n-N}}{n!(N-n)!}=\frac{x^{-N}(1+x^2)^N}{N!}$$ Ahora diferenciar con respecto a $x$ para conseguirlo: $$\sum_{n=0}^{N}\frac{(2n-N)x^{2n-N-1}}{n!(N-n)!}=\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]$$

Multiplicar por $x$ para conseguirlo: $$\sum_{n=0}^{N}\frac{(2n-N)x^{2n-N}}{n!(N-n)!}=x\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]$$

Diferenciar con respecto a $x$ para conseguirlo:

$$\sum_{n=0}^{N}\frac{(2n-N)^2x^{2n-N-1}}{n!(N-n)!}=\frac{d}{dx}[x\frac{d}{dx}[\frac{x^{-N}(1+x^2)^N}{N!}]]$$

Ahora dejemos que $x=1$ para obtener su suma en el LHS.

Answer 4

$$ \begin{align} \sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!} &= \sum_{n=0}^N\frac{((N-n)-n)^2}{n!(N-n)!} \\ &= \sum_{n=0}^N\frac{(N-n)^2}{n!(N-n)!}+\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=0}^N\frac{(N-n)n}{n!(N-n)!} \\ &= \sum_{n=0}^N\frac{n^2}{n!(N-n)!}+\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=1}^{N-1}\frac1{(n-1)!(N-n-1)!} \\ &= 2\sum_{n=0}^N\frac{n^2}{n!(N-n)!}-2\sum_{n=0}^{N-2}\frac1{n!(N-2-n)!}\;. \end{align} $$

Ahora considere

$$ \sum_{n=0}^m\binom mnq^n=(1+q)^m $$

y por lo tanto

$$ \sum_{n=0}^m\frac{q^n}{n!(m-n)!}=\frac{(1+q)^m}{m!}\;. $$

Aplicando $q\partial/\partial q$ dos veces da como resultado

$$ \sum_{n=0}^m\frac{n^2q^n}{n!(m-n)!}=\frac{(1+q)^{m-1}}{(m-1)!}+q^2\frac{(1+q)^{m-2}}{(m-2)!}\;. $$

Ahora, el ajuste $q=1$ rinde

$$ \sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!}=2\left(\frac{2^{N-1}}{(N-1)!}+\frac{2^{N-2}}{(N-2)!}\right)-2\frac{2^{N-2}}{(N-2)!}=\frac{2^N}{(N-1)!}\;. $$

Answer 5

En el transcurso de este puesto , se puede ver cómo demostrar que $$\sum_{n=0}^Nn\binom{N}{n}=N2^{N-1}.\tag{1}$$ Otros dos datos interesantes que utilizaremos son $$\sum_{n=0}^N\binom{N}{n}=2^N\tag{2}$$ y $$\binom{N+1}{n}=\binom{N}{n}+\binom{N}{n-1}.\tag{3}$$ A partir de estos hechos, junto con $\binom{N}{N+1}=0$ vemos que $$\begin{align}\sum_{n=0}^{N+1}n^2\binom{N+1}{n} &= \sum_{n=0}^{N+1}n^2\binom{N}{n} + \sum_{n=0}^{N+1}n^2\binom{N}{n-1}\\ &= \sum_{n=0}^Nn^2\binom{N}{n} + \sum_{n=1}^{N+1}n^2\binom{N}{n-1}\\ &= \sum_{n=0}^Nn^2\binom{N}{n} + \sum_{n=0}^N(n+1)^2\binom{N}{n}\\ &= 2\sum_{n=0}^Nn^2\binom{N}{n} + 2\sum_{n=0}^Nn\binom{N}{n}+\sum_{n=0}^N\binom{N}{n}\\ &= 2\sum_{n=0}^Nn^2\binom{N}{n} + N2^N+2^N\\ &= (N+1)2^N+2\sum_{n=0}^Nn^2\binom{N}{n}.\end{align}$$ Tenga en cuenta que $\sum_{n=0}^0n^2\binom{0}{n}=0=0(0+1)2^{0-2}$ y si $\sum_{n=0}^Nn^2\binom{N}{n}=N(N+1)2^{N-2}$ entonces por el trabajo anterior, $$\begin{align}\sum_{n=0}^{N+1}n^2\binom{N+1}{n} &= (N+1)2^N+2\sum_{n=0}^Nn^2\binom{N}{n}\\ &= (N+1)2^N+N(N+1)2^{N-1}\\ &= (N+1)(N+2)2^{N-1},\end{align}$$ por lo que inductivamente, tenemos la identidad $$\sum_{n=0}^Nn^2\binom{N}{n}=N(N+1)2^{N-2}\tag{4}$$ para todos $N\geq 0$ .

Ahora, utilizando $(1)$ $(2)$ y $(4)$ podemos ver que $$\begin{align}N!\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!} &= \sum_{n=0}^N(N-2n)^2\binom{N}{n}\\ &= N^2\sum_{n=0}^N\binom{N}{n}-4N\sum_{n=0}^Nn\binom{N}{n}+4\sum_{n=0}^Nn^2\binom{N}{n}\\ &= N^22^N-N^22^{N+1}+N(N+1)2^N\\ &= N2^N,\end{align}$$ por lo que dividiendo por $N!$ rinde $$\sum_{n=0}^N\frac{(N-2n)^2}{n!(N-n)!} = \frac{2^N}{(N-1)!},$$ como se desee.