Hallar el sumatorio del elemento máximo de subconjuntos de un conjunto

Question

Sea $S={1,2,...,j}$ Para cada subconjunto no vacío de $A$ de $S$ dejemos $m(A)$ denotan el elemento máximo de $A$ Entonces encuentra $$\sum_{\text{over all subsets of S}} m(A)$$

Viendo la respuesta pude demostrar fácilmente por inducción que el sumatorio es igual a $$(j-1)2^j+1$$ Pero me encuentro con dificultades para evaluarlo realmente sin conocer ya el resultado.He intentado trabajar con muchos casos pero he fracasado.Alguna idea?Gracias.

Answer 1

Ordenar los elementos de $S$ en orden decreciente.

Toma el primer elemento $j$ que es el mayor, y hallar todos los subconjuntos del conjunto $S-\{j\}$ y poner $j$ en cada uno de ellos. Todos ellos tendrían $j$ como máximo. El número de subconjuntos es $2^{j-1}$ . Multiplicándolo por $j$ daría $j2^{j-1}$ que forma parte de $\sum_{\text{over all subsets of S}} m(A)$ .

Haga lo mismo con $j-1$ para el conjunto $S-\{j,j-1\}$ . Usted obtiene

$(j-1)2^{j-2}$

Por lo tanto, tienes que calcular la siguiente suma.

$\sum_{i=1}^{j}i2^{i-1}$

Para ello, puede escribirla como una función de $x$

$f(x)=\sum_{i=1}^{j}ix^{i-1}$

Entonces, $F(x)=\sum_{i=1}^{j}x^{i}$ y $F'(x)=f(x)$

Utilizando la fórmula de la suma de series geométricas

$F(x)=\frac{x^{j+1}-x}{x-1}$

$F'(x)=\frac{(x-1)[(j+1)x^j-1]-x^{j+1}+x}{(x-1)^2}$

Por último, debe realizar la siguiente evaluación

$f(2)=F'(2)$