Prove que D_{n}=n D_{n-1}+(-1)^{n}, para n \geq 2.

Passo 1

O enunciado pede para provar a seguinte relação para o número de desarranjos D_n, isto é, o número de permutações de n elementos sem pontos fixos:
D_{n} \;=\; n\,D_{n-1} \;+\;(-1)^{n},\quad n\ge2.
O conteúdo que vamos usar é a fórmula por inclusão–exclusão para D_n, que vale
D_n \;=\; n!\;\sum_{k=0}^{n} \frac{(-1)^k}{k!}.

Passo 2

Aplique a mesma fórmula para D_{n-1}. Temos
D_{n-1} \;=\;(n-1)!\;\sum_{k=0}^{\,n-1} \frac{(-1)^k}{k!}.

Passo 3

Multiplique essa expressão por n:
n\,D_{n-1} \;=\;n\,(n-1)!\;\sum_{k=0}^{\,n-1} \frac{(-1)^k}{k!} \;=\;n!\;\sum_{k=0}^{\,n-1} \frac{(-1)^k}{k!}.

Passo 4

Compare agora D_n e n\,D_{n-1}. Pela fórmula de D_n,
D_n \;=\;n!\;\sum_{k=0}^{n} \frac{(-1)^k}{k!} \;=\;n!\;\sum_{k=0}^{\,n-1} \frac{(-1)^k}{k!} \;+\;n!\;\frac{(-1)^n}{n!}.
Reconhecendo que o primeiro termo é exatamente n\,D_{n-1}, obtemos
D_n \;=\;n\,D_{n-1} \;+\;(-1)^n.

Resposta

D_{n}=n\,D_{n-1}+(-1)^{n},\quad n\ge2.

Exercícios relacionados