Cómo probar que $\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n)$

Question

Sé que $$\sum_{k=0}^n \binom nk k^2=2^{n-2}(n^2+n),$$, pero no puedo encontrar una manera de cómo demostrarlo. Traté de inducción, pero no funcionó. En la wiki dicen que yo debería usar la diferenciación, pero no sé cómo aplicarlo a coeficiente binomial.
Gracias por la respuesta.

(Presunta) Fuente: Ejercicio Teórico 1.12(b), P18, Un Primer Curso en Pr, 8ª Ed, por S Ross

Answer 1

Esto es equivalente a probar $$\sum_{k=0}^n k^2 {n\choose k}=n(n+1)2^{n-2}.$$ Given $n$ people we can form a committee of $k$ people in ${n\elegir k}$ ways. Once the committee is formed we can pick a committee leader and a committee planner. If we allow each person to hold both job titles there are $k$ ways for this to happen. If no person is allowed to have both job titles, then there are $k$ choices for the committee leader and $k-1$ choices for the committee planner for a total of $k(k-1)$ choices for a different committee leader and committee planner. The total number of choices for a committee leader and a committee planner is $k+k(k-1)=k^2$ . We now sum for all possible $k$ values from $0$ to $n$ to form every committee of $k$ people with a committee leader and a committee planner, that is, $\sum_{k=0}^n k^2 {n\elegir k}$. We can count the same thing by first picking committee leaders and committee planners and then filling in the committee with the remaining people. If we allow each person to hold both job titles, then there are $n$ ways for this to be done. The remaining $n-1$ people can form the committee in $2^{n-1}$ ways since each person has two choices, either they are in the committee or they are not in the committee. The total number of committees where each person can hold both titles is $n2^{n-1}$. If no person is allowed to hold both job titles, then there are $n$ choices for a committee leader and $n-1$ choices for a committee planner. The remaining $n-2$ people can form the committee in $2^{n-2}$ ways since each person has two choices, either they are in the committee or they are not in the committee. The total number of ways to form a committee where no person can have both job titles is $n(n-1)2^{n-2}$. Thus the total number of ways to form the committee is $n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$. Hence $\sum_{k=0}^n k^2 {n\elegir k}=n(n+1)2^{n-2}$.

Otra forma de hacerlo es considerar $$(1+x)^n=\sum_{k=0}^n {n\choose k}x^k.$$ Differentiating both sides with respect to $x$ we obtain $$n(1+x)^{n-1}=\sum_{k=1}^n k{n\choose k}x^{k-1}.$$ Multiplying both sides of the equation by $x$ and differentiating with respect to $x$ we obtain $$n(1+x)^{n-1}+nx(n-1)(1+x)^{n-2}=\sum_{k=1}^nk^2{n\choose k}x^{k-1}.$$ Letting $x=1$ and simplifying the left-hand side we see that $$n(n+1)2^{n-2}=\sum_{k=1}^n k^2{n\choose k}.$$

Answer 2

Dilip comentario de puntos a la forma estándar. Aquí va una forma alternativa:

Si usted está familiarizado con la probabilidad de base, usted debe reconocer un canónica de la distribución Binomial en $$ \frac{1}{2^n} {n \choose k}$$

que contar el número de éxitos en $n$ ensayos de un experimento con prob. $=1/2$ . Este Binomio puede ser también considerado como la suma de $n$ iid variables de Bernoulli con $p=1/2$. Por lo tanto, la media es $n p = n/2$ y la varianza $n p (1-p)= n/4$

Por lo tanto el segundo momento es

$$ E[X^2]=\frac{1}{2^n} \sum_{k=0}^n {n \choose k} k^2 = (E[X])^2+\sigma^2_X = n^2 \frac{1}{4} + n \frac{1}{4} = 2^{-2}(n^2+n)$$

Answer 3

Una forma común de tratar con esto es mediante la generación de función.

En este problema, la clave es generar la $k^2$ factor en la suma. Aviso si usted tiene un polinomio $P(z) = \sum_{k=0}^n a_k z^k$$z$, cada vez que aplicar el operador $z\frac{d}{dz}$, $z^k$ plazo recogerá un factor adicional $k$. Más exactamente, usted va a tener

$$\left(z\frac{d}{dz}\right)^m P(z) = \sum_{k=0}^n a_k k^m z^k$$

Con esto en mente, uno encontrar $$\begin{align} \sum_{k=0}^n \binom{n}{k} k^2 z^k = & \sum_{k=0}^n \binom{n}{k} \left(z\frac{d}{dz}\right)^2 z^k = \left(z\frac{d}{dz}\right)^2 \sum_{k=0}^n \binom{n}{k} z^k\\ = & \left(z\frac{d}{dz}\right)^2 (1+z)^n = z\frac{d}{dz} nz(1+z)^{n-1}\\ = & z \left( n(1+z)^{n-1} + n(n-1)z(1+z)^{n-2}\right) \end{align}$$ Tomando $z = 1$ en ambos lados, uno conseguir $$\sum_{k=0}^n \binom{n}{k} k^2 = n 2^{n-1} + n(n-1) 2^{n-2} = (n^2 + n) 2^{n-2}$$

Answer 4

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

La primera suma es dado por $P(n)$, mientras que

$$\sum_{j=0}^{n} \binom {n}{j} (j+1)^2=\sum_{j=0}^{n} \binom {n}{j} j^2+2\sum_{j=0}^{n} \binom {n}{j} j+\sum_{j=0}^{n} \binom {n}{j} 1$$

Usted sabe lo $\sum_{j=0}^{n} \binom {n}{j} j^2$ $\sum_{j=0}^{n} \binom {n}{j}$ son por lo tanto para demostrar $P(n+1)$ usted necesita para mostrar algo como esto:

$$\sum_{j=0}^{n} \binom {n}{j} j=\mbox{something} \,.$$

Ahora de nuevo en uso de la inducción y $\binom {n+1}{j}=\binom {n}{j}+\binom {n}{j-1}$.