Prove que
para
.
Passo 1
O enunciado trata dos números de derangement (permutações sem ponto fixo)
e pede para provar a relação de recorrência
válida para todo
. Para isso vamos usar o princípio da inclusão-exclusão, que fornece uma forma fechada para
.
Passo 2
Pelo princípio da inclusão-exclusão, o número de permutações de
elementos sem ponto fixo é
Passo 3
Multiplicando a expressão acima para
por
, obtemos
Passo 4
Agora basta somar
a
:
Isso mostra exatamente que