Considere todos os subconjuntos não vazios de \{1,2,3, \ldots, n\}. Para cada destes subconjuntos, calculamos o produto de seus elementos. Prove que a soma de todos os produtos obtidos é (n+1)!-1

Passo 1

O enunciado dá o conjunto \{1,2,3,\ldots,n\}. 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
(n+1)!-1.
Informações relevantes dadas pelo enunciado:
  • Estamos considerando todos os subconjuntos não vazios de \{1,2,\ldots,n\}.
  • Para cada subconjunto S tomamos o produto \prod_{i\in S} i.
  • 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
\prod_{k=1}^{n} (1+k).
Explico por quê esse produto é útil: ao multiplicar fator a fator e expandir usando a propriedade distributiva, de cada fator (1+k) escolhemos ou o termo 1 (que corresponde a não incluir o número k no subconjunto) ou o termo k (que corresponde a incluir k no subconjunto). Cada termo produzido pela expansão é, portanto, o produto de alguns dos k's escolhidos, isto é, o produto dos elementos de algum subconjunto S\subseteq\{1,\dots,n\}. Assim, a expansão gera exatamente todos os produtos \prod_{i\in S} i para todos os subconjuntos S (incluindo o subconjunto vazio).

Passo 3

Formalizando a ideia do Passo 2, temos a igualdade (pela expansão termo a termo)
\prod_{k=1}^{n} (1+k)=\sum_{S\subseteq\{1,\dots,n\}} \prod_{i\in S} i.
Aqui a soma à direita inclui também o subconjunto vazio. Pelo costume combinatório, o produto sobre o subconjunto vazio é 1. Portanto, a soma sobre todos os subconjuntos não vazios é essa soma total menos 1:
\sum_{\substack{S\subseteq\{1,\dots,n\}\\\ S\neq\varnothing}} \prod_{i\in S} i \;=\; \prod_{k=1}^{n} (1+k) - 1.

Passo 4

Agora calculamos explicitamente o produto do lado direito. Reescrevendo os fatores:
\prod_{k=1}^{n} (1+k)=\prod_{k=1}^{n} (k+1).
Fazendo a mudança de índice j=k+1 obtemos
\prod_{k=1}^{n} (k+1)=\prod_{j=2}^{n+1} j.
Pelo significado de fatorial, \prod_{j=1}^{n+1} j=(n+1)!. Como \prod_{j=2}^{n+1} j é o mesmo produto sem o fator j=1, concluímos
\prod_{j=2}^{n+1} j=(n+1)!.

Passo 5

Juntando o que obtivemos no Passo 3 com o resultado do Passo 4, temos
\sum_{\substack{S\subseteq\{1,\dots,n\}\\\ S\neq\varnothing}} \prod_{i\in S} i \;=\; (n+1)!-1.
Isso é exatamente o que o enunciado pede. Para ficar mais concreto e motivador, veja o caso n=3: os subconjuntos não vazios de \{1,2,3\} têm produtos 1,2,3,1\cdot2,1\cdot3,2\cdot3,1\cdot2\cdot3, ou seja 1,2,3,2,3,6,6 cuja soma é 23. E (3+1)!-1=24-1=23, conferindo o resultado.

Resposta

(n+1)!-1

Exercícios relacionados