*22. Demonstre o princípio da inclusão-exclusão usando a indução matemática.

Passo 1

O enunciado pede para demonstrar, por indução em n, o princípio da inclusão-exclusão que dá a cardinalidade da união de n conjuntos A_1,\dots,A_n. Vamos provar que
\left|\bigcup_{i=1}^n A_i\right| =\sum_{r=1}^n(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n}\bigl|A_{i_1}\cap\cdots\cap A_{i_r}\bigr|.

Passo 2

Base da indução n=2. Para dois conjuntos A_1,A_2 sabemos que
|A_1\cup A_2|=|A_1|+|A_2|-|A_1\cap A_2|.
Isso coincide com a fórmula para n=2, pois o somatório interno para r=1 |A_1|+|A_2| e para r=2 -|A_1\cap A_2|.

Passo 3

Passo indutivo: suponha que o resultado valha para qualquer coleção de n-1 conjuntos. Ou seja, para A_1,\dots,A_{n-1} temos
\Bigl|\bigcup_{i=1}^{n-1}A_i\Bigr| =\sum_{r=1}^{n-1}(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n-1}\! \bigl|A_{i_1}\cap\cdots\cap A_{i_r}\bigr|.

Passo 4

Considere agora n conjuntos A_1,\dots,A_n. Defina
U=\bigcup_{i=1}^{n-1}A_i.
Então queremos calcular \bigl|U\cup A_n\bigr|. Pelo caso n=2 (união de U com A_n) vale
|U\cup A_n|=|U|+|A_n|-|U\cap A_n|.

Passo 5

Pela hipótese indutiva substituímos |U| e expandimos |U\cap A_n|. Primeiro
|U| =\sum_{r=1}^{n-1}(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n-1}\! \bigl|A_{i_1}\cap\cdots\cap A_{i_r}\bigr|.
Além disso
U\cap A_n =\bigl(\!\!\bigcup_{i=1}^{n-1}A_i\bigr)\cap A_n =\bigcup_{i=1}^{n-1}(A_i\cap A_n),
que é a união de n-1 conjuntos A_i\cap A_n. Logo, pela hipótese indutiva aplicada a eles,
|U\cap A_n| =\sum_{r=1}^{n-1}(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n-1}\! \bigl|A_{i_1}\cap\cdots\cap A_{i_r}\cap A_n\bigr|.

Passo 6

Agora junte tudo em
|U\cup A_n| =|U|+|A_n|-|U\cap A_n|
e observe que:
– O termo |A_n| corresponde ao caso r=1 das interseções que envolvem A_n sozinho.
– O somatório de |U| traz todas as interseções de tamanho r dentre os primeiros n-1 conjuntos.
– O -|U\cap A_n| insere todas as interseções que incluem A_n e mais r outros, com sinal (-1)^r.
Reagrupando os somatórios por número r de conjuntos intersectados, obtemos exatamente
\left|\bigcup_{i=1}^n A_i\right| =\sum_{r=1}^{n}(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n} \bigl|A_{i_1}\cap\cdots\cap A_{i_r}\bigr|.
Isso finaliza a indução.

Resposta

\boxed{ \left|\bigcup_{i=1}^n A_i\right| =\sum_{r=1}^n(-1)^{\,r-1} \sum_{1\le i_1<\cdots<i_r\le n} \bigl|A_{i_1}\cap\cdots\cap A_{i_r}\bigr| }.

Exercícios de Livros Relacionados