Hey there! Sign in to join this conversationNew here? Join for free

Mathematical Thinking: 2 Derangements/proof questions Watch

    • Thread Starter
    Offline

    2
    ReputationRep:
    ..
    Offline

    0
    ReputationRep:
    (Original post by Lewk)
    [COLOR="Teal"]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!))
    [/COLOR]

    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 + rep
    Double-check your post; there's a lot of question-marks so it's hard to know what's being asked.
    • PS Helper
    Offline

    0
    ReputationRep:
    maths is lame.
    • Thread Starter
    Offline

    2
    ReputationRep:
    (Original post by Dream Eater)
    Double-check your post; there's a lot of question-marks so it's hard to know what's being asked.
    oh yeah sorry the question marks are usually always minus signs, thanks for pointing out
    Offline

    0
    ReputationRep:
    (Original post by Lewk)
    oh yeah sorry the question marks are usually always minus signs, thanks for pointing out
    Unless I'm wrong, there is an implicit assumption in the first answer that d(0) = 1. Did you maybe miss this out from the question before?

    Edit: Also, how familiar are you with proof by induction?
    Offline

    0
    ReputationRep:
    Edit: I'm stupidies, but induction still works. I think you need to assume d(0) = 1 though. Label the following equations (A) and (B) respectively:

    (A) \qquad \qquad d(n) = (n - 1) (d(n - 1) + d(n - 2))

    (B) \qquad \qquad \qquad d(n) = nd(n - 1) + (-1)^n

    You have already proved (A); you want to prove (B) for all n\geq 2, and induction is the best way. See if you can show d(1) = 0 from equation (A) -- it takes about one line. Then put n = 2 in equation (A) to get:

    d(2) = d(1) + d(0) = d(0)

    so d(2) = d(0). Since d(0) = 1, this agrees with the answer you'd get from (B). So (B) holds in the initial case when n = 2. Now, assume that equation (B) holds for n = k-1; we want to prove the same equation holds for n=k. So let n=k in equation (A) and rearrange a little to get:

     d(k) - kd(k-1) = -d(k-1) + (k-1) d(k-2).

    But we know what d(k-1) is from our assumption, so we substitute that into the above equation. You should then get, with a little work:

     d(k) - kd(k-1) = -(-1)^{k-1} = (-1)^k,

    and this proves that the equation holds for all n \geq 2, by induction.

    The second equation should also be proved by induction, as the question itself says. So prove it for n = 1, then assume true for n = k-1, and show it for n = k, etc.
    • PS Helper
    Offline

    0
    ReputationRep:
    so lame
 
 
 
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • Poll
    Did TEF Bronze Award affect your UCAS choices?
    Useful resources

    Make your revision easier

    Maths

    Maths Forum posting guidelines

    Not sure where to post? Read the updated guidelines here

    Equations

    How to use LaTex

    Writing equations the easy way

    Student revising

    Study habits of A* students

    Top tips from students who have already aced their exams

    Study Planner

    Create your own Study Planner

    Never miss a deadline again

    Polling station sign

    Thinking about a maths degree?

    Chat with other maths applicants

    Can you help? Study help unanswered threads

    Groups associated with this forum:

    View associated groups
  • See more of what you like on The Student Room

    You can personalise what you see on TSR. Tell us a little about yourself to get started.

  • The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

    Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

    Quick reply
    Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.