Given that $D_0 = 1, D_1 = 0, D_n = (n-1)(D_{n-1}+D_{n-2})$ for all $n\geq 2$.

Prove the equality $$D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$$

I wish to prove the equalty using Complete Induction.

Let $P(n)$ be the above statement for $n\geq 2$.

Basis Step: $P(0)$ and $P(1)$ are true by the initial conditions.

Inductive step: Let $l\geq 1$ be fixed. Suppose that $P(m)$ is true for all $0\leq m \leq l$.

LHS of $P(l+1) = l \cdot (D_l + D_{l-1}) = (l+1)! \sum_{k=0}^{l}\dfrac{(-1)^k}{k!} + l!\cdot \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!}$

From there, I have tried to simplify the expression and equate it to the RHS of $P(l+1)$ but I can't get the RHS.

Any help please?

Edit: I managed to solve it after correcting my mistake. Thanks :)

  • 2
    $\begingroup$ In your attempt, $(l+1)!$ should be $l.l!$. $\endgroup$ – José Carlos Santos Nov 24 '17 at 7:27
  • 1
    $\begingroup$ In order to give the context of the issue, $D_n$ is a number of "Derangements" of $n$ objects. Googling with this keyword (coming from combinatorics) plus the word "recurrence", you will find many connections. $\endgroup$ – Jean Marie Nov 24 '17 at 7:32
  • $\begingroup$ @JoséCarlosSantos Oh yes, let me attempt on solving it again. $\endgroup$ – Little Rookie Nov 24 '17 at 7:34
  • $\begingroup$ For more about this sum see for example this thread. $\endgroup$ – Raymond Manzoni Nov 24 '17 at 7:35

\begin{eqnarray*} l \cdot (D_l + D_{l-1}) &=&\color{red}{l (l)!} \sum_{k=0}^{l}\dfrac{(-1)^k}{k!} + l!\cdot \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} \\ &=&(l+1) (l)! \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} + \dfrac{(-1)^l l l!}{l!} \\ &=&(l+1) ! \sum_{k=0}^{l-1}\dfrac{(-1)^k}{k!} + \dfrac{(-1)^l (l+1)l!}{ l!}- \dfrac{(-1)^l l!}{l!} \\ &=&(l+1)! \sum_{k=0}^{l+1}\dfrac{(-1)^k}{k!} = \color{blue}{D_{l+1}}. \\ \end{eqnarray*}

  • $\begingroup$ I have managed to solve it after correcting my mistake. Thanks for the help anyway. $\endgroup$ – Little Rookie Nov 24 '17 at 8:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.