Results 1 to 2 of 2

Thread: Mathematical Thinking: 2 Derangements/proof questions

  1. #1
    Dec 2010

    Question Mathematical Thinking: 2 Derangements/proof questions

    d(n) = (n − 1) (d(n − 1) + d(n − 2))

    a) By considering d(n)−nd(n−1), use the formula above repeatedly to show that d(n)
    satisfies the (first order) recurrence relation

    d(n) = nd(n - 1) + (-1)^n, for n>=2

    b) Use the previous part to show by induction that, for n >= 1, d(n) satisfies the explicit

    d(n) = n!(1-(1/1!)+(1/2!)-(1/3!)+(1/4!)-...+((-1)^n)/n!))

    I was just about able to prove the formula at the top in a question before this (after a lot of help) which was very difficult, hopefully these 2 questions won't be as hard but i have no idea how to begin. Any help would be great
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Oct 2009
    First, judging by the explicit formula for $\displaystyle d_n$, we have $\displaystyle d_1=0$ and $\displaystyle d_2=1$. (This information should have been given explicitly in the beginning of the problem.) Either from the explicit formula or from the recurrence equation one can calculate that $\displaystyle d_3=2$, $\displaystyle d_4=9$, etc. Therefore, $\displaystyle d_2=2d_1+1$ and $\displaystyle d_3=3d_2-1$, which fits the general law $\displaystyle d_n = nd_{n - 1} + (-1)^n$ that we have to show.

    Next, from the original equation we get $\displaystyle d_n-nd_{n-1}=-(d_{n-1}+(n-1)d_{n-2})$. The right-hand side looks like the left-hand side where n has been replaced by n - 1. By continuing this way, we indeed can arrive at $\displaystyle d_n-nd_{n-1}=\pm(d_2-2d_1)=\pm 1$.

    I think it is easier to prove $\displaystyle d_n-nd_{n-1}=(-1)^n$ by induction. Both the base case and the induction step have been shown above.

    Proving the explicit formula by induction is also straightforward. Follow the general outline: identify the induction statement P(n); prove the base case P(1); fix an arbitrary n, assume P(n - 1) and use it to prove P(n). If you have difficulties, post what you have done and the description of the difficulty.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: Dec 10th 2010, 11:38 AM
  2. Derangements(help me asap)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Feb 13th 2010, 01:07 AM
  3. Number of derangements of n objects
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: Feb 10th 2010, 08:16 AM
  4. mathematical statistics questions in matematica
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Jan 26th 2010, 08:44 AM
  5. Best way to develop your mathematical thinking.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: Oct 30th 2008, 04:53 PM

Search Tags

/mathhelpforum @mathhelpforum