*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
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