Prove que Dn=n Dn-1+(-1)^n para n >= 2.

Passo 1

O enunciado trata dos números de derangement (permutações sem ponto fixo) Dn e pede para provar a relação de recorrência
Dn ;=; n,Dn-1 ;+;(-1)^n,
válida para todo n>=2. Para isso vamos usar o princípio da inclusão-exclusão, que fornece uma forma fechada para Dn.

Passo 2

Pelo princípio da inclusão-exclusão, o número de permutações de n elementos sem ponto fixo é
Dn =;n! ;-;binom n1 (n-1)! ;+;binom n2 (n-2)! ;-cdots+(-1)^nbinom nn0! =;n!sumk=0^n(-1)^kk!,

Passo 3

Multiplicando a expressão acima para Dn-1 por n, obtemos
n,Dn-1 =;n,(n-1)!sumk=0^,n-1(-1)^kk! =;n!sumk=0^,n-1(-1)^kk!,

Passo 4

Agora basta somar (-1)^n a n,Dn-1:
n,Dn-1+(-1)^n =;n!sumk=0^,n-1(-1)^kk! ;+;(-1)^n =;n!sumk=0^n(-1)^kk! =;Dn,
Isso mostra exatamente que
Dn=n,Dn-1+(-1)^n,

Resposta

Dn=n,Dn-1+(-1)^n(forall n>=2)

Exercícios de Livros Relacionados