¿Cómo se prueba, usando la inducción, que [matemáticas] \ displaystyle \ sum _ {\ varnothing \ subsetneq S \ subseteq \ {1, \ ldots, n \}} \ prod_ {a \ in S} \ frac {1} {a } = n [/ matemáticas]?

Answer 1

Creo que el símbolo que necesita es simplemente “no es igual”, la suma se lleva a cabo en todos los subconjuntos no vacíos de [math] {1, \ ldots, n} [/ math]. Tenga en cuenta en primer lugar que hay [matemáticas] 2 ^ n-1 [/ matemáticas] tales subconjuntos. Imaginemos lo que sucedería si se permitiera que el subconjunto [math] S [/ math] estuviera vacío. Entonces el término del producto es un producto de cero elementos. Es justo suponer que dicho producto se evalúa como 1. Sea [math] f (n) [/ math] el valor de esta suma, incluido ese subconjunto vacío. Estamos buscando demostrar que [matemáticas] f (n) = n + 1 [/ matemáticas], para todos los números naturales [matemáticas] n [/ matemáticas].

Ahora el paso de inducción. Supongamos que [matemática] f (k) = k + 1 [/ matemática] para algún número natural [matemática] k [/ matemática]. Mire los subconjuntos de [math] {1, \ ldots, k + 1} [/ math]. Se dividen precisamente en dos categorías: las que no contienen [matemáticas] k + 1 [/ matemáticas], y las que sí lo hacen. Convenientemente, podemos hacer coincidir cada uno de los subconjuntos en cada una de estas dos categorías con exactamente un subconjunto de [math] {1, \ ldots, k} [/ math].

Ahora expandamos [matemáticas] f (k + 1) [/ matemáticas]. Los subconjuntos que no contienen [matemática] k + 1 [/ matemática] contribuyen exactamente [matemática] f (k) [/ matemática] a la suma. Todos los subconjuntos restantes tendrán una [matemática] \ frac {1} {k + 1} [/ matemática] adicional en su término de producto. Por lo tanto, [matemáticas] f (k + 1) = f (k) + \ frac {f (k)} {k + 1} = f (k) \ cdot \ frac {k + 2} {k + 1} = k +2 [/ matemáticas]. Por lo tanto, si suponemos [matemática] f (k) = k + 1 [/ matemática], entonces [matemática] f (k + 1) = k + 2 [/ matemática]. Esa es la inducción. Finalmente, para comenzar a rodar la pelota, notamos que [matemáticas] f (1) = 2 [/ matemáticas] y la prueba de inducción está completa.

Finalmente, excluya el conjunto vacío y obtendrá el resultado.