Considere todos os subconjuntos do conjunto
que não contêm números consecutivos. Prove que a soma dos quadrados dos produtos dos números nesses subconjuntos é igual a (
)! - 1 .
Passo 1
O enunciado pede para somar, em todos os subconjuntos não consecutivos de
, o quadrado do produto dos elementos e mostrar que esse total vale
. O conteúdo usado será: (1) separar os subconjuntos em dois casos — os que contêm
e os que não contêm
— para montar uma relação de recorrência; (2) resolver a recorrência por indução.
Passo 2
Denotemos por
o somatório desejado (excluímos o conjunto vazio para que o resultado final seja
e não precise ajustar constantes).
Passo 3
Se
não contém
, então
é um subconjunto não consecutivo de
e sua contribuição soma exatamente
.
Se contém
, então obrigatoriamente não contém
, e escrevemos
em que
é também não consecutivo (podendo ser vazio). Nesse caso
Se
e ao somar sobre todos os
, incluindo o vazio, obtemos
Portanto a recorrência fica
Passo 4
Verificamos as condições iniciais:
Para , os subconjuntos não vazios são só
, contribuição
, logo
. E
.
Para , os subconjuntos não vazios sem consecutivos são
e
, soma
. E
.
Para
Para
Passo 5
Fazemos indução em
. Suponha que para
e
valha
Então pela recorrência
Agrupando termos:
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
é