よくある具体例として、
n人でプレゼント交換を行ったとき、自分のプレゼントをもらわない場合の数をD(n)とおく。
全員を、「1番目、2番目、…、i番目、…n番目」としたとき、
n番目の人とi番目の人がプレゼントを相互交換した場合と、n番目の人のプレゼントをi番目の人が貰わない場合に、場合分けをします。

①n番目の人とi番目の人がプレゼントを相互交換した場合
残りのn-2人が自分のプレゼントをもらわない場合の数は、D(n-2)と書け、n番目の人とプレゼントを相互交換するのは、i番目の人も含めてn-1人いるので、
(n-1)×D(n-2)通り
と書けます。

②n番目の人のプレゼントをi番目の人が貰わなない場合
n番目の人がi番目の人のプレゼントを貰い、i番目の人がn番目の人のプレゼントを貰わなかったとします。n番目以外のn-1人はすべて自分のプレゼントを貰わないので、その場合の数はD(n-1)と書け、さらにn番目の人は、i番目を含めた(自分を除く)n-1人のプレゼントを貰う可能性があるので、
(n-1)×D(n-1)通り
と書けます。

よって、
D(n)＝(n-1)×D(n-2)+(n-1)×D(n-1)
　　＝(n-1)×{D(n-2)+D(n-1)}
となります