Inducción: $\sum_{k=0}^n \binom nk k^2 = n(1+n)2^{n-2}$

Question

He encontrado loco (al menos para mí) es la inducción de ejemplo, en el hecho de que sólo sería bueno para probar. (Incluso a tener problemas con el arranque) todas las sugerencias son altamente valorados: $$0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}=n(1+n)2^{n-2} $$

Answer 1

Recuento de la cardinalidad de a $S=\left\{(A,x,y): A \subseteq \{1,2,\dots,n\} \wedge x,y \in A\right\}$ en dos formas diferentes:

Forma 1. Si $A$ $k$ elementos, entonces usted tiene $k^2$ opciones para $x,y$$n \choose k$$A$. Por lo $|S|=\sum_{k} k^2 {n \choose k}$.

Forma 2. Dos casos:

• Si $x=y$, luego tenemos a $n$ opciones para $x$ $2^{n-1}$ opciones para $A$.

• Si $x \neq y$, luego tenemos a $n(n-1)$ opciones para $x,y$ $2^{n-2}$ opciones para $A$.

Por lo tanto,$|S|=n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$.

Answer 2

Marvis ha dado un típico excelente respuesta. Voy a seguir adelante y mostrar una inducción al estilo de la prueba, en caso de que usted está interesado.

Un útil básica combinatoric hecho para esta inducción es la prueba de la identidad de Pascal: $$\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}\tag{1}$$ Another nice basic fact is $$\sum_{k=0}^n\binom{n}k=2^n\tag{2}$$ for all $n\in\Bbb$N.

Para cada una de las $n$, definir $$f(n)=n(1+n)2^{n-2}\qquad \text{and}\qquad g(n)=\sum_{k=0}^nk^2\binom{n+1}{k},$$ so what we're trying to show is that $f(n)=g(n)$ for all $n$. In the $n=0$ caso, esto está claro, ¿sí?

Para la inducción de paso, suponiendo que $f(n)=g(n)$ algunos $n$, debemos mostrar que $f(n+1)=g(n+1)$.

Observar, por un lado, que $$f(n+1)=(n+1)(2+n)2^{n-1}=(n+1)2^n+n(n+1)2^{n-1}=(n+1)2^n+2f(n),$$ so by inductive hypothesis, $$2g(n)=2f(n)=f(n+1)-(n+1)2^n.\tag{3}$$ On the other hand, we have $$\begin{align}g(n+1) &= \sum_{k=0}^{n+1}k^2\binom{n+1}k\\ &=\sum_{k=1}^{n+1}k^2\binom{n+1}{k}\\ &=(n+1)^2\binom{n+1}{n+1}+\sum_{k=1}^nk^2\binom{n+1}{k}\\ &\overset{(1)}{=}(n+1)^2+\sum_{k=1}^nk^2\left[\binom{n}{k}+\binom{n}{k-1}\right]\\ &=(n+1)^2+\sum_{k=1}^nk^2\binom{n}{k}+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+\sum_{k=0}^nk^2\binom{n}{k}+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+g(n)+\sum_{k=1}^nk^2\binom{n}{k-1}\\ &=(n+1)^2+g(n)+\sum_{k=0}^{n-1}(k+1)^2\binom{n}{k}\\ &=n^2+2n+1+g(n)+\sum_{k=0}^{n-1}k^2\binom{n}{k}+2\sum_{k=0}^{n-1}k\binom{n}{k}+\sum_{k=0}^{n-1}\binom{n}{k}\\ &=(n^2+2n+1)\binom{n}{n}+g(n)+\sum_{k=0}^{n-1}k^2\binom{n}{k}+2\sum_{k=0}^{n-1}k\binom{n}{k}+\sum_{k=0}^{n-1}\binom{n}{k}\\ &=g(n)+\sum_{k=0}^nk^2\binom{n}{k}+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &=2g(n)+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &\overset{(3)}{=}f(n+1)-(n+1)2^n+2\sum_{k=0}^nk\binom{n}{k}+\sum_{k=0}^n\binom{n}{k}\\ &\overset{(2)}{=}f(n+1)-n2^n+2\sum_{k=0}^nk\binom{n}{k}\\ &=f(n+1)-2\left(n2^{n-1}-\sum_{k=0}^nk\binom{n}{k}\right)\end{align}$$ Hence, to see that $f(n+1)=g(n+1)$, it suffices that $$n2^{n-1}=\sum_{k=0}^nk\binom{n}{k}$$ Indeed, note that for $1\leq k\leq n$ we have $$k\binom{n}{k}=k\cdot\frac{n!}{k!(n-k)!}=n\cdot\frac{(n-1)!}{(k-1)!\bigl((n-1)-(k-1)\bigr)!}=n\binom{n-1}{k-1},\tag{4}$$ and so $$\begin{align}n2^{n-1} &\overset{(2)}{=} n\sum_{k=0}^{n-1}\binom{n-1}{k}\\ &= n\sum_{k=1}^n\binom{n-1}{k-1}\\ &= \sum_{k=0}^{n-1}n\binom{n-1}{k-1}\\ &\overset{(4)}{=} \sum_{k=1}^nk\binom{n}{k}\\ &= \sum_{k=0}^nk\binom{n}{k},\end{align}$$ como se desee.

Answer 3

He aquí una puramente combinatoria argumento de que evita casi todos los cálculos.

Una cierta escuela elige a cero o más miembros de su clase que se graduó a la sociedad de honor. También otorga un premio en matemáticas y un premio en inglés; estos siempre van a miembros de la sociedad de honor, pero pueden ir a la misma persona. Si hay $n$ de los estudiantes en la clase de graduación, ¿en cuántas formas diferentes puede la entrega de premios y la membresía en la sociedad de honor será otorgada?

• Supongamos que $k$ de los estudiantes son admitidos a la sociedad de honor: se puede elegir en $\binom{n}k$ formas, y los dos premios que se pueden hacer en $k^2$ maneras. Desde $k$ puede estar en el rango de $0$ a través de$n$, $\sum_{k=0}^nk^2\binom{n}k$ formas de otorgar los premios y de la membresía.

• Alternativamente, podemos decidir primero que obtiene los premios.

  1. Si van a la misma persona, no se $n$ formas de elegir a esa persona. El destinatario de la entrega de premios debe ser elegido por el honor de la sociedad, y cualquiera de los otros $n-1$ de los estudiantes puede ser elegido, por lo que hay $n2^{n-1}$ posibles combinaciones de este tipo.

  2. Si van a diferentes personas, que puede ser otorgado en $n(n-1)$ maneras diferentes, y debemos, a continuación, elija cualquier subconjunto de los restantes $2^{n-2}$ a los estudiantes a llenar el honor de la sociedad; hay $n(n-1)2^{n-2}$ maneras de hacer esto.

  Este llega a un total de $$n2^{n-1}+n(n-1)2^{n-2}=(2+n-1)n2^{n-2}=n(n+1)2^{n-2}$$ formas de otorgar los premios y membresías.

De ello se desprende que $$\sum_{k=0}^nk^2\binom{n}k=n(n+1)2^{n-2}\;,$$ desde los dos lados representan diferentes maneras de contar la misma cosa.

Answer 4

Con la inducción se demuestra que:

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

Para las pruebas utilizamos la identidad de Pascal: $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$.

1. Si $\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2^n$ $$\binom{n+1}{0}+\binom{n+1}{1}+\binom{n+1}{2}+\cdots+\binom{n+1}{n}+\binom{n+1}{n+1}=\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{0}+\binom{n}{2}+\binom{n}{1}+\cdots+\binom{n}{n}+\binom{n}{n-1}+\binom{n}{n}=\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}+\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n-1}+\binom{n}{n}=2^n+2^n=2^{n+1}.$$
2. Si $0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}=n2^{n-1}$ $$0\binom{n+1}{0}+1\binom{n+1}{1}+2\binom{n+1}{2}+\cdots+n\binom{n+1}{n}+(n+1)\binom{n+1}{n+1}=\\ \ldots = \\ 2\left(0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}\right)+\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=2n2^{n-1}+2^n=(n+1)2^n.$$
3. Si $0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}=n(1+n)2^{n-2} $ $$0^2\binom{n+1}{0}+1^2\binom{n+1}{1}+2^2\binom{n+1}{2}+\cdots+n^2\binom{n+1}{n}+(n+1)^2\binom{n+1}{n+1}=\\ \ldots =\\ 2\left( 0^2\binom{n}{0}+1^2\binom{n}{1}+2^2\binom{n}{2}+\cdots+n^2\binom{n}{n}\right)+\\ 2\left(0\binom{n}{0}+1\binom{n}{1}+2\binom{n}{2}+\cdots+n\binom{n}{n}\right)+\\ \binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots+\binom{n}{n}=\\ 2n(1+n)2^{n-2}+2n2^{n-1}+2^n=(n+1)(2+n)2^{n-1} $$