Considere todos os subconjuntos do conjunto \{1,2, \ldots, n\} que não contêm números consecutivos. Prove que a soma dos quadrados dos produtos dos números nesses subconjuntos é igual a ( n+1 )! - 1 .

Passo 1

O enunciado pede para somar, em todos os subconjuntos não consecutivos de \{1,2,\dots,n\}, o quadrado do produto dos elementos e mostrar que esse total vale (n+1)!-1. O conteúdo usado será: (1) separar os subconjuntos em dois casos — os que contêm n e os que não contêm n — para montar uma relação de recorrência; (2) resolver a recorrência por indução.

Passo 2

Denotemos por
S_n \;=\;\sum_{\substack{A\subset\{1,\dots,n\}\A\text{ não tem elementos consecutivos}\A\neq\emptyset}} \bigl(\!\!\prod_{a\in A}a\bigr)^2
o somatório desejado (excluímos o conjunto vazio para que o resultado final seja (n+1)!-1 e não precise ajustar constantes).

Passo 3

Se A não contém n, então A é um subconjunto não consecutivo de \{1,\dots,n-1\} e sua contribuição soma exatamente S_{n-1}.
Se A contém n, então obrigatoriamente não contém n-1, e escrevemos A = B\cup\{n\} em que B\subset\{1,\dots,n-2\} é também não consecutivo (podendo ser vazio). Nesse caso
\bigl(\prod_{a\in A}a\bigr)^2 =\bigl(n\cdot\prod_{b\in B}b\bigr)^2 =n^2\;\bigl(\prod_{b\in B}b\bigr)^2,
e ao somar sobre todos os B, incluindo o vazio, obtemos
\sum_{B\subset\{1,\dots,n-2\}} n^2\bigl(\prod_{b\in B}b\bigr)^2 \;=\; n^2\Bigl(1 + \sum_{\substack{B\neq\emptyset\B\text{ não consecutivo}}} \bigl(\prod_{b\in B}b\bigr)^2\Bigr) \;=\; n^2\bigl(1 + S_{n-2}\bigr).
Portanto a recorrência fica
S_n \;=\; S_{n-1} \;+\; n^2\bigl(1+S_{n-2}\bigr) \;=\; S_{n-1} + n^2\,S_{n-2} + n^2.

Passo 4

Verificamos as condições iniciais:
Para n=1, os subconjuntos não vazios são só \{1\}, contribuição 1^2=1, logo S_1=1. E (1+1)!-1=2-1=1.
Para n=2, os subconjuntos não vazios sem consecutivos são \{1\} e \{2\}, soma 1^2+2^2=5. E (2+1)!-1=6-1=5.

Passo 5

Fazemos indução em n. Suponha que para n-1 e n-2 valha
S_{n-1}=(n)!-1, \quad S_{n-2}=(n-1)!-1.
Então pela recorrência
S_n = S_{n-1} + n^2\,S_{n-2} + n^2 = \bigl(n! - 1\bigr) + n^2\bigl((n-1)! - 1\bigr) + n^2.
Agrupando termos:
S_n = n! -1 + n^2\,(n-1)! - n^2 + n^2 = n! + n^2\,(n-1)! -1 = (n-1)!\bigl(n + n^2\bigr)-1 = (n-1)!\,n(n+1) -1 = (n+1)! -1.
Logo a fórmula se mantém, encerrando a indução.

Resposta

A soma dos quadrados dos produtos de todos os subconjuntos sem elementos consecutivos de \{1,2,\dots,n\} é
(n+1)! - 1.

Exercícios relacionados