Regla de la suma y $\sum_{k=1}^n (n-k)2^{k-1}$

Question

Intento obtener una forma cerrada para $\sum_{k=1}^n (n-k)2^{k-1}$ mediante un argumento combinatorio. Desgraciadamente, nada parece dar en el clavo. Si escribo esto como $n\sum 2^{k-1}-\sum k2^{k-1}$ entonces sí tengo el primer término $n\sum 2^{k-1}=n2^{n+1}-n2^n-n$ pero soy incapaz de encontrarle sentido al segundo término.

¿Puede alguien ayudar, por favor?

Answer 1

Pista:

¿Cuántas secuencias binarias de longitud $n$ contienen al menos dos 0, con el segundo 0 en la posición $n-k+1$ ?

Answer 2

CONSEJO: Deja que $S=\{1,2,\dots,n\}$ . Para cada $k\in S$ , $(n-k)2^{k-1}$ es el número de maneras de elegir cualquier subconjunto de $\{1,\dots,k-1\}$ y un elemento cualquiera de $\{k+1,k+2,\dots,n\}$ . Este es exactamente el número de maneras de elegir un subconjunto $A$ de $S$ tal que $|A|\ge 2$ y el segundo mayor elemento de $A$ es $k$ . Sea $\mathscr{A}_k$ es la familia de subconjuntos de $S$ . Si elige un subconjunto de $S$ de cardinalidad mínima $2$ pertenece a un único $\mathscr{A}_k$ . Por lo tanto, la suma es el número de subconjuntos de $S$ de cardinalidad mínima $2$ ¿Cuál es...?

Answer 3

Comience con $$ \sum_{k=1}^n x^k=\frac{x^{n+1}-x}{x-1}\tag{1} $$ a continuación, tomar la derivada y multiplicar por $x$ : $$ \sum_{k=1}^n kx^k=\frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\tag{2} $$ Resta $(2)$ de $n$ veces $(1)$ para obtener $$ \begin{align} \sum_{k=1}^n(n-k)x^k &=\frac{nx^{n+2}-nx^{n+1}-nx^2+nx}{(x-1)^2}-\frac{nx^{n+2}-(n+1)x^{n+1}+x}{(x-1)^2}\\ &=\frac{x^{n+1}-nx^2+(n-1)x}{(x-1)^2}\tag{3} \end{align} $$ Enchufe $x=2$ en $(3)$ produce $$ \sum_{k=1}^n(n-k)2^k=2^{n+1}-2n-2\tag{4} $$

Answer 4

Un comentario sobre la respuesta de robjohn:

Si $f(x) = \sum_{k=1}^n k x^k $ , y $g(x) = \sum_{k=1}^n (n-k) x^k $ , entonces

$\begin{align} f(x)x^{-n} &=\sum_{k=1}^n k x^{k-n}\\ &=\sum_{k=0}^{n-1} (n-k) x^{-k}\\ &=\sum_{k=0}^{n} (n-k) x^{-k}\\ &=n+\sum_{k=1}^{n} (n-k) x^{-k}\\ &=n+g(1/x)\\ \end{align} $

así que $f(1/x)x^n = n+g(x)$ o $g(x) = x^n f(1/x) - n$ .