Results 1 to 2 of 2

Math Help - Mathematical Thinking: 2 Derangements/proof questions

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    3

    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
    equation


    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
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773
    First, judging by the explicit formula for d_n, we have d_1=0 and 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 d_3=2, d_4=9, etc. Therefore, d_2=2d_1+1 and d_3=3d_2-1, which fits the general law d_n = nd_{n - 1} + (-1)^n that we have to show.

    Next, from the original equation we get 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 d_n-nd_{n-1}=\pm(d_2-2d_1)=\pm 1.

    I think it is easier to prove 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: December 10th 2010, 11:38 AM
  2. Derangements(help me asap)
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 13th 2010, 01:07 AM
  3. Number of derangements of n objects
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: February 10th 2010, 08:16 AM
  4. mathematical statistics questions in matematica
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: January 26th 2010, 08:44 AM
  5. Best way to develop your mathematical thinking.
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: October 30th 2008, 04:53 PM

Search Tags


/mathhelpforum @mathhelpforum