Encuentra una suma cerrada: $\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}$

Question

Al analizar el tiempo de ejecución de un algoritmo, utilicé un argumento de recuento para llegar a esta expresión:

$$\sum_{j=1}^{n}(j-1)\,2^{j-1}\,\left(\frac{k}{2}\right)^{\underline{j-1}}\,(k-j)^{\underline{n-j}}=k^{\underline{n}} - 2^n\left(\frac{k}{2}\right)^{\underline{n}}$$

Esto es válido siempre que $k>n$ y $k$ es par. Las potencias subrayadas son potencias decrecientes.

Mi pregunta es: si no conociera de antemano esta suma cerrada, ¿cómo podría encontrarla?

Answer 1

Escribamos $k=2 m$ ya que $k$ se supone par: $$ e_j = (j-1) 2^{j-1} \left(\frac{k}{2}\right)^{\underline{j-1}} (k-j)^{\underline{n-j}} = (j-1) 2^{j-1} m^{\underline{j-1}} (2m-j)^{\underline{n-j}} $$ En suma indefinida $\sum_j e_j$ puede calcularse utilizando Algoritmo de Gosper es decir, encontrar una función racional tal $R(j)$ eso: $$ \sum_j e_j = R(j) e_j $$ o lo que es lo mismo, resolviendo: $$ R(j+1) e_{j+1} - R(j) e_{j} = e_j $$ Grados límite del numerador y el denominador de la función racional $R(j)$ es fácil adivinar que $$ R(j) = \frac{j-2k+1}{j-1} $$ encaja a la perfección. Entonces $$ \sum_{j=1}^n e_j = R(n+1) e_{n+1} - R_{1} e_1 $$