Suma de coeficientes binomiales por un polinomio

Question

¿Existe una expresión cerrada para,

$\displaystyle\sum_{k=0}^n {n\choose k}k^2$

Sostiene que,

$\displaystyle\sum_{k=0}^n {n\choose k}k=n2^{n-1}$

¿Existe una generalización para las titulaciones superiores?

Answer 1

Coeficientes binomiales como polinomios

Tenga en cuenta que $$ \binom{k}{j}=\frac{k(k-1)\cdots(k-j+1)}{j!}\tag{1} $$ $\binom{k}{j}$ puede considerarse un grado $j$ polinomio en $k$ . Podemos escribir cualquier grado $j$ polinomio en $k$ como combinación lineal de $\binom{k}{0}$ , $\binom{k}{1}$ , $\dots$ , $\binom{k}{j}$ . Por ejemplo, $$ \begin{align} 1&=\binom{k}{0}\\ k&=\binom{k}{1}\\ k^2&=2\binom{k}{2}+\binom{k}{1}\\ \end{align}\tag{2} $$

---

Multiplicación de un coeficiente binomial $$ \begin{align} k\binom{k}{j} &=\left[(j+1)\frac{k+1}{j+1}-1\right]\binom{k}{j}\tag{3a}\\ &=(j+1)\binom{k+1}{j+1}-\binom{k}{j}\tag{3b}\\ &=(j+1)\binom{k}{j+1}+(j+1)\binom{k}{j}-\binom{k}{j}\tag{3c}\\ &=(j+1)\binom{k}{j+1}+j\binom{k}{j}\tag{3d} \end{align} $$ Explicación:
$(3a)$ : reescritura creativa de $k$
$(3b)$ : $\binom{k+1}{j+1}=\frac{k+1}{j+1}\binom{k}{j}$
$(3c)$ : $\binom{k+1}{j+1}=\binom{k}{j+1}+\binom{k}{j}$
$(3d)$ : álgebra

---

Aplicación de $\boldsymbol{(3)}$

Podemos ampliar recursivamente la lista iniciada en $(2)$ : $$ \begin{align} k^3 &=k\cdot k^2\\ &=2k\binom{k}{2}+k\binom{k}{1}\\ &=2\left(3\binom{k}{3}+2\binom{k}{2}\right)+\left(2\binom{k}{2}+\binom{k}{1}\right)\\ &=6\binom{k}{3}+6\binom{k}{2}+\binom{k}{1}\tag{4} \end{align} $$ $$ \begin{align} k^4 &=k\cdot k^3\\ &=6k\binom{k}{3}+6k\binom{k}{2}+k\binom{k}{1}\\ &=6\left(4\binom{k}{4}+3\binom{k}{3}\right)+6\left(3\binom{k}{3}+2\binom{k}{2}\right)+\left(2\binom{k}{2}+\binom{k}{1}\right)\\ &=24\binom{k}{4}+36\binom{k}{3}+14\binom{k}{2}+\binom{k}{1}\tag{5} \end{align} $$

---

Cómo ayuda

Una vez que hemos escrito el polinomio como una combinación lineal de coeficientes binomiales, podemos utilizar la siguiente fórmula para simplificar las sumas finales: $$ \begin{align} \sum_{k=0}^n\binom{n}{k}\binom{k}{j} &=\sum_{k=0}^n\binom{n}{j}\binom{n-j}{k-j}\\ &=\binom{n}{j}2^{n-j}\tag{6} \end{align} $$

---

Aplicación a la pregunta

Podemos aplicar las fórmulas derivadas anteriormente para obtener las siguientes generalizaciones

$$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^2 &=\sum_{k=0}^n\binom{n}{k}\left(2\binom{k}{2}+\binom{k}{1}\right)\\ &=2\binom{n}{2}2^{n-2}+\binom{n}{1}2^{n-1}\\ &=\bbox[5px,border:2px solid #C0A000]{2^{n-1}\left(\binom{n}{2}+\binom{n}{1}\right)}\tag{7} \end{align} $$ $$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^3 &=\sum_{k=0}^n\binom{n}{k}\left(6\binom{k}{3}+6\binom{k}{2}+\binom{k}{1}\right)\\ &=6\binom{n}{3}2^{n-3}+6\binom{n}{2}2^{n-2}+\binom{n}{1}2^{n-1}\\ &=\bbox[5px,border:2px solid #C0A000]{2^{n-2}\left(3\binom{n}{3}+6\binom{n}{2}+2\binom{n}{1}\right)}\tag{8} \end{align} $$ $$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^4 &=\sum_{k=0}^n\binom{n}{k}\left(24\binom{k}{4}+36\binom{k}{3}+14\binom{k}{2}+\binom{k}{1}\right)\\ &=24\binom{n}{4}2^{n-4}+36\binom{n}{3}2^{n-3}+14\binom{n}{2}2^{n-2}+\binom{n}{1}2^{n-1}\\ &=\bbox[5px,border:2px solid #C0A000]{2^{n-1}\left(3\binom{n}{4}+9\binom{n}{3}+7\binom{n}{2}+\binom{n}{1}\right)}\tag{9} \end{align} $$

Las fórmulas anteriores pueden ampliarse para dar fórmulas para polinomios de grado tan alto como se desee.

---

Uso de los números Stirling

Números Stirling de segunda clase nos permite escribir fácilmente monomios como combinaciones lineales de coeficientes binomios con la siguiente fórmula $$ \newcommand{\stirtwo}[2]{\left\{{#1}\atop{#2}\right\}} k^j=\sum_{i=0}^ji!\stirtwo{j}{i}\binom{k}{i}\tag{10} $$ Sumando, obtenemos $$ \begin{align} \sum_{k=0}^n\binom{n}{k}k^jx^k &=\sum_{k=0}^n\binom{n}{k}\sum_{i=0}^ji!\stirtwo{j}{i}\binom{k}{i}x^k\\ &=\sum_{i=0}^ji!\stirtwo{j}{i}\sum_{k=0}^n\binom{n}{k}\binom{k}{i}x^k\\ &=\sum_{i=0}^ji!\stirtwo{j}{i}\sum_{k=0}^n\binom{n}{i}\binom{n-i}{k-i}x^k\\ &=\bbox[5px,border:2px solid #C0A000]{(1+x)^n\sum_{i=0}^ji!\stirtwo{j}{i}\binom{n}{i}\left(\frac x{1+x}\right)^i}\tag{11} \end{align} $$ Fórmulas $(7)$ - $(9)$ puede derivarse de $(11)$ estableciendo $x=1$ .

Answer 2

Para una solución diferente para un caso general que el dado por @JackD'Aurizio desea transformar el polinomio $p(k)$ en la expresión

$$\sum_k\binom{n}{k}p(k)$$

en un polinomio basado en factoriales decrecientes . Por ejemplo

$$\sum_k\binom{n}{k}k^2=\sum_k\binom{n}{k}(k^{\underline{2}}+k)$$

Entonces la suma binomial se puede simplificar extrayendo factoriales decrecientes de $n$ de la suma y (probablemente) cambiando el índice de las sumas.

Pasar de $p(k)$ a un "polinomio" de factoriales decrecientes necesitarás saber que

$$k^n=\sum_j \left\{{ n\atop j }\right\}k^{\underline j}$$

para $n\ge 0$ donde los símbolos $\left\{{ n\atop j }\right\}$ son Números de Stirling del segundo tipo .

Este enlace tienen un algoritmo fácil para pasar un polinomio entero a un "polinomio" de factoriales decrecientes.

Answer 3

Para el factor $k$ ,

$$\sum_{k=1}^n {n\choose k}k=\sum_{k=1}^n \frac{n!}{(n-k)!k!}k =n\sum_{k=1}^n \frac{(n-1)!}{(n-k)!(k-1)!}\\ =n\sum_{k=0}^{n-1} {n\choose k}=n2^{n-1}.$$

Del mismo modo para $(k-1)k$ ,

$$\sum_{k=2}^n {n\choose k}(k-1)k=\sum_{k=1}^n \frac{n!}{(n-k)!k!}(k-1)k=(n-1)n\sum_{k=1}^n \frac{(n-2)!}{(n-k)!(k-2)!}\\ =(n-1)n\sum_{k=0}^{n-2} {n\choose k}=(n-1)n2^{n-2}.$$

En términos más generales,

$$\sum_{k=m}^n {n\choose k}(k-m+1)\cdots(k-1)k\\ =\sum_{k=1}^n \frac{n!}{(n-k)!k!}(k-m+1)\cdots(k-1)k\\ =(n-m+1)\cdots(n-1)n\sum_{k=1}^n \frac{(n-m)!}{(n-k)!(k-m)!}\\ =(n-1)n\sum_{k=0}^{n-m} {n\choose k}=(n-m+1)(n-1)n2^{n-m}.$$

Entonces,

$$k^2=(k-1)k+k,\\ k^3=(k-2)(k-1)k+3k^2-2k=(k-2)(k-1)k+3(k-1)k+k\\ \cdots$$ y puedes convertir cualquier polinomio en una suma de factoriales decrecientes.

Obsérvese que el $m$ los primeros términos de las sumas deben sumarse por separado.