Considere todos os subconjuntos não vazios de
. Para cada destes subconjuntos, calculamos o produto de seus elementos. Prove que a soma de todos os produtos obtidos é
Passo 1
O enunciado dá o conjunto
. Para cada subconjunto não vazio desse conjunto calculamos o produto dos seus elementos e somamos esses produtos. A pergunta é: mostrar que essa soma vale
Informações relevantes dadas pelo enunciado:
- Estamos considerando todos os subconjuntos não vazios de
. - Para cada subconjunto
tomamos o produto . - Queremos a soma desses produtos sobre todos os subconjuntos não vazios.
Passo 2
Vou construir uma expressão cuja expansão gera exatamente todos esses produtos (incluindo o produto vazio). Considere o produto
Explico por quê esse produto é útil: ao multiplicar fator a fator e expandir usando a propriedade distributiva, de cada fator
escolhemos ou o termo
(que corresponde a não incluir o número
no subconjunto) ou o termo
(que corresponde a incluir
no subconjunto). Cada termo produzido pela expansão é, portanto, o produto de alguns dos
's escolhidos, isto é, o produto dos elementos de algum subconjunto
. Assim, a expansão gera exatamente todos os produtos
para todos os subconjuntos
(incluindo o subconjunto vazio).
Passo 3
Formalizando a ideia do Passo 2, temos a igualdade (pela expansão termo a termo)
Aqui a soma à direita inclui também o subconjunto vazio. Pelo costume combinatório, o produto sobre o subconjunto vazio é
. Portanto, a soma sobre todos os subconjuntos não vazios é essa soma total menos
:
Passo 4
Agora calculamos explicitamente o produto do lado direito. Reescrevendo os fatores:
Fazendo a mudança de índice
obtemos
Pelo significado de fatorial,
. Como
é o mesmo produto sem o fator
, concluímos
Passo 5
Juntando o que obtivemos no Passo 3 com o resultado do Passo 4, temos
Isso é exatamente o que o enunciado pede. Para ficar mais concreto e motivador, veja o caso
: os subconjuntos não vazios de
têm produtos
, ou seja
cuja soma é
. E
, conferindo o resultado.