Linear second-order recurrence sequence

Maths and statistics discussion, revision, exam and homework help.

Announcements Posted on
Enter our travel-writing competition for the chance to win a Nikon 1 J3 camera 21-05-2013
IMPORTANT: You must wait until midnight (morning exams)/4.30AM (afternoon exams) to discuss Edexcel exams and until 1pm/6pm the following day for STEP and IB exams. Please read before posting, including for rules for practical and oral exams. 28-04-2013
Search Thread
Advanced Search
Sign in to Reply
  1. SubAtomic's Avatar
    1 20-06-2012  15:49
    • Exalted and Worshipped Member
    • Posts: 1,316
    Linear second-order recurrence sequence
    #Edit: Changed to undergrad because it seems not many if any have seen this in sixth form.

    Hi, having a brain malfunction with this as am not quite understanding. Maybe am brain fluffing on some basic indices? Not quite understanding the RHS.

    To find a closed form for a linear second-order recurrence system:

    \displaystyle u_0=a \ , \ u_1=b \ , \ \boxed{u_{n+2}=pu_{n+1}+qu_n(*)} \ \ (n=0,1,2...)

    Step 1 Write down the auxiliary equation:

    \displaystyle r^2-pr-q=0

    Step 2 Solve the auxiliary equation:

    \displaystyle r= \alpha \ \ \ \ \ \mathrm{and} \ \ \ \ \ \ r= \beta

    Step 3 Write down the general solution with unkown constants A and B.

    \displaystyle \boxed{ \alpha \ , \ \beta \ \mathrm{real\ and\ distinct}| \ \ u_n=A \alpha ^n + B \beta ^n}
    \displaystyle \boxed{ \alpha= \beta \ , \ \ \mathrm{repeated\ root}| \ \ u_n=(A+Bn) \alpha ^n }
    \displaystyle \boxed{ \mathrm{no\ real\ solutions} | \ \ \ \ \ \mathrm{more\ complicated}}

    Step 4 Use initial terms \displaystyle u_0=a \ , \ u_1=b to find A and B.



    Why does \displaystyle u_n=n \alpha ^n \ \mathrm{satisfy} \ (*) \ \mathrm{if} \ \alpha \ \mathrm{is\ a\ repeated\ root} \ ?

    Auxiliary equation: \displaystyle (r- \alpha)^2=r^2-2\alpha r+\alpha ^2=0 \ \ \ \ \ \ \ \ \ \ \ \ \boxed{p=2 \alpha \ , \ q=- \alpha ^2}


    Recurrence relation: \displaystyle u_{n+2}=2 \alpha u_{n+1}-\alpha ^2 u_n \ \ \ \ \ \ \ (t)


    \displaystyle \mathrm{substitute} \ u_n=n\alpha ^n \implies u_{n+1}=(n+1) \alpha ^{n+1} am I right in my implies here?

    Maybe getting it a bit more now after typing it out but still unsure.

    So with a bracket like this \displaystyle 2a(b+1)a \ , \mathrm{would\ I\ have} \ 2ab+2a+ab+a=3ab+3a \ ?

    No I'd have \displaystyle 2a^2(b+1)


    Check:

    \displaystyle \mathrm{RHS\ of\ (t)} \ \ \ \ \ =2\alpha (n+1) \alpha^{n+1}-\alpha ^2n\alpha ^n \ \ \ \ \ \ \ \ \ \ \boxed{\mathrm{substitute} \ \ u_n=n \alpha ^n}

    \displaystyle =2n\alpha ^{n+2}+2\alpha ^{n+2}-n\alpha ^{n+2} \\ \\ =(n+2) \alpha ^{n+2}=u_{n+2}= \mathrm{LHS\ of\ (t)}

    :facepalm: think I get it now, maybe:confused: maybe not :eek4:.

    Missed how the last term of the second line takes the first term coefficient down to 1:rolleyes:

    Still feel a bit puzzled.
    Last edited by SubAtomic; 04-07-2012 at 18:29.
  2. SubAtomic's Avatar
    2 20-06-2012  18:28
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    Please. Any takers?

    (Original post by nuodai)
    ...

    (Original post by notnek)
    ...
    neg: Really? Tool
    Last edited by SubAtomic; 09-07-2012 at 19:07.
    Post rating:
    1
  3. raheem94's Avatar
    3 20-06-2012  21:49
    • TSR Demigod
    • Posts: 5,512
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    Any takers?
    Which equation is ( * ) \ ?
  4. raheem94's Avatar
    4 20-06-2012  22:13
    • TSR Demigod
    • Posts: 5,512
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    The only equation on the page with the * next to it is this and it is layed out like this

    \displaystyle u_0=a \ , \ u_1=b \ , \ \boxed{u_{n+2}=pu_{n+1}+qu_n(*)} \ \ (n=0,1,2...)

    And then a little box with a few things in like this

    \displaystyle \boxed{ \alpha \ , \ \beta \ \mathrm{real\ and\ distinct}| \ \ u_n=A \alpha ^n + B \beta ^n}
    \displaystyle \boxed{ \alpha= \beta \ , \ \ \mathrm{repeated\ root}| \ \ u_n=(A+Bn) \alpha ^n }
    \displaystyle \boxed{ \mathrm{no\ real\ solutions} | \ \ \ \ \ \mathrm{more\ complicated}}
    I haven't covered this topic, so sorry i can't help.

    Hopefully someone else will help you.
    Post rating:
    1
  5. SubAtomic's Avatar
    5 20-06-2012  22:15
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by raheem94)
    I haven't covered this topic, so sorry i can't help.

    Hopefully someone else will help you.
    Ok cheers for looking mate.

    :emo:
  6. SubAtomic's Avatar
    6 21-06-2012  12:36
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by BabyMaths)
    If \alpha is a root of r^2-pr-q=0 whether it's repeated or not it follows that A\alpha^n(\alpha^2-p\alpha-q)=0 and an extra factor of n isn't going to change that. An\alpha^n(\alpha^2-p\alpha-q)=0 and so An\alpha^{n+2}=p An\alpha^{n+1}+q An\alpha^{n} and so u_n=An\alpha^n satisfies u_{n+2}=pu_{n+1}+qu_n.

    Does that answer your question?

    There is a more interesting question to ask here.
    Thanks for the reply:cool:

    Was going to completely change my post and break it into what I don't quite get.

    So will go from the first things just to clarify.

    I think I was multiplying this out wrong to start off. Everything above is copied from a book so I tried working through it and that is where I became confused.

    Realised after messing about last night that I was expanding the bracket wrong.

    So I thought this

    \displaystyle 2\alpha (n+1) \alpha^{n+1}-\alpha ^2n\alpha ^n=\ 2n\alpha+2\alpha+n\alpha ^{n+1}+\alpha ^{n+1}-\alpha ^2n\alpha ^n

    Which is wrong, yes, or am I making a newb error?

    So I'd have been better bringing the \displaystyle \alpha ^{n+1} to the right hand side to start with?

    So I'd have had


    \displaystyle 2\alpha ^{n+2} (n+1)-\alpha ^2n\alpha ^n

    And is this line mathematically correct

    \displaystyle u_n=n\alpha ^n \implies u_{n+1}=(n+1) \alpha ^{n+1}
    Last edited by SubAtomic; 21-06-2012 at 12:44.
  7. FranticMind's Avatar
    7 21-06-2012  12:42
    • Overlord in Training
    • Posts: 3,044
    Re: Linear second-order recurrence sequence
    Also please don't use * for anything other than conjugate.
    Post rating:
    2
  8. SubAtomic's Avatar
    8 21-06-2012  12:43
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by FranticMind)
    Also please don't use * for anything other than conjugate.
    :confused: what do you mean?
  9. BabyMaths's Avatar
    9 21-06-2012  12:44
    • Peer Of The TSR Realm
    • Posts: 1,567
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    So I'd have been better bringing the \displaystyle \alpha ^{n+1} to the right hand side to start with?

    So I'd have had


    \displaystyle 2\alpha ^{n+2} (n+1)-\alpha ^2n\alpha ^n

    And is this line mathematically correct

    \displaystyle u_n=n\alpha ^n \implies u_{n+1}=(n+1) \alpha ^{n+1}
    Yes to everything here.
  10. SubAtomic's Avatar
    10 21-06-2012  12:46
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by BabyMaths)
    Yes to everything here.
    Thanks, that is where most of my confusion came from.

    So what is the more interesting question to ask :holmes:
  11. BabyMaths's Avatar
    11 21-06-2012  12:58
    • Peer Of The TSR Realm
    • Posts: 1,567
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    So is this correct too then?


    \displaystyle 2\alpha ^{n+2} (n+1)-\alpha ^2n\alpha ^n=2n\alpha+2\alpha+n\alpha ^{n+1}+\alpha ^{n+1}-\alpha ^2n\alpha ^n
    I'm not sure what you're trying to do.

    \displaystyle 2\alpha ^{n+2} (n+1)-\alpha ^2n\alpha ^n= 2\alpha ^{n+2} (n+1)-n\alpha ^{n+2}=2\alpha^{n+2}

    The more interesting question I had in mind was why the solution in the case of repeated roots is u_n=(A+Bn)\alpha^n.
  12. SubAtomic's Avatar
    12 21-06-2012  13:11
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by BabyMaths)
    I'm not sure what you're trying to do.
    Just trying to understand what I was thinking the other day, because I was way off the mark it seems.


    (Original post by BabyMaths)
    \displaystyle 2\alpha ^{n+2} (n+1)-\alpha ^2n\alpha ^n= 2\alpha ^{n+2} (n+1)-n\alpha ^{n+2}=2\alpha^{n+2}
    Do you mean \displaystyle (n+2) \alpha ^{n+2}

    (Original post by BabyMaths)
    The more interesting question I had in mind was why the solution in the case of repeated roots is u_n=(A+Bn)\alpha^n.
    No idea That is a question for you to answer Will have to dwell on this or maybe I will have a better idea once I have finished the block I am currently on.

    Thanks a lot for clarifying those things though:cool:

    All the best.
    Last edited by SubAtomic; 21-06-2012 at 13:54.
  13. BabyMaths's Avatar
    13 21-06-2012  14:54
    • Peer Of The TSR Realm
    • Posts: 1,567
    Re: Linear second-order recurrence sequence
    Sorry, my post that you +repped was rubbish.

    I will try to redeem myself.

    With the proposed solution (A+Bn)\alpha^n

    We have

    u_{n+2}=(A+B(n+2))\alpha^{n+2}

    u_{n+1}=(A+B(n+1))\alpha^{n+1}

    u_{n}=(A+Bn)\alpha^{n}

    Subbing these in u_{n+2}=pu_{n+1}+qu_n we get (A+B(n+2))\alpha^{n+2}=p(A+B(n+1 ))\alpha^{n+1}+q(A+Bn)\alpha^{n}.

    Collecting terms and factorising a bit..

    A\alpha^n(\alpha^2-p\alpha-q)+Bn\alpha^n(\alpha^2-p\alpha-q)+B\alpha^{n+1}(2\alpha-p)=0

    and we know that 2\alpha-p=0 since we have equal roots and also \alpha^2-p\alpha-q=0 so u_n=(A+Bn)\alpha^n satisfies u_{n+2}=pu_{n+1}+qu_n.


    Edit: I missed a B.
    Last edited by BabyMaths; 21-06-2012 at 21:10.
  14. raheem94's Avatar
    14 21-06-2012  14:58
    • TSR Demigod
    • Posts: 5,512
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    :confused: what do you mean?
    I think he meant stuff like complex conjugate. Example 2 + i is a conjugate of 2 - i
  15. SubAtomic's Avatar
    15 21-06-2012  16:56
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by BabyMaths)
    Sorry, my post that you +repped was rubbish.

    I will try to redeem myself.

    With the proposed solution (A+Bn)\alpha^n

    We have

    u_{n+2}=(A+B(n+2))\alpha^{n+2}

    u_{n+1}=(A+B(n+1))\alpha^{n+1}

    u_{n}=(A+Bn)\alpha^{n}

    Subbing these in u_{n+2}=pu_{n+1}+qu_n we get (A+B(n+2))\alpha^{n+2}=p(A+B(n+1 ))\alpha^{n+1}+q(A+Bn)\alpha^{n}.

    Collecting terms and factorising a bit..

    A\alpha^n(\alpha^2-p\alpha-q)+Bn\alpha^n(\alpha^2-p\alpha-q)+\alpha^{n+1}(2\alpha-p)=0

    and we know that 2\alpha-p=0 since we have equal roots and also \alpha^2-p\alpha-q=0 so u_n=(A+Bn)\alpha^n satisfies u_{n+2}=pu_{n+1}+qu_n.
    Wonderful, + repped you for your time but this has made things much clearer, your explanation is better than the book, thanks:cool:



    (Original post by raheem94)
    I think he meant stuff like complex conjugate. Example 2 + i is a conjugate of 2 - i
    Well he wasted his time telling me that because I don't have complex numbers until the final block:rolleyes:

    Thought it'd be clear what it meant.
    Last edited by SubAtomic; 28-06-2012 at 17:54.
  16. SubAtomic's Avatar
    16 28-06-2012  18:12
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    Hi, not quite sure what my book is saying here.

    I have a table, Coefficients p and q, Initial values a and b, and

    Apparent pattern in U^2_n+U^2_{n+1}

    Both coefficients have value 1, Initial values a=0 and b=1.

    So this is what the book says under the 'apparent pattern' section,

    it is every other term of U_n , starting with U_3

    Will post some screen shots of what mathcad shows. I don't get it, what does it mean it is every other term of U_n , starting with U_3.

    The first screen shot is of p=1, q=1, a=0, b=1.
    Attached Thumbnails
    Click image for larger version.  Name: tsr 1.PNG  Views: 27  Size: 12.6 KB  ID: 160284   Click image for larger version.  Name: tsr 2.PNG  Views: 19  Size: 12.7 KB  ID: 160285   Click image for larger version.  Name: tsr 3.PNG  Views: 26  Size: 12.9 KB  ID: 160286   Click image for larger version.  Name: tsr 4.PNG  Views: 14  Size: 12.4 KB  ID: 160287  
  17. sputum's Avatar
    17 29-06-2012  12:28
    • Adored and Respected Member
    • Posts: 425
    Re: Linear second-order recurrence sequence
    Good old Mathcad
    could you post a book/page ref if it's MS221?
  18. SubAtomic's Avatar
    18 29-06-2012  16:05
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by sputum)
    Good old Mathcad
    could you post a book/page ref if it's MS221?
    Lol, I bought the materials for 221 online to go through before October.

    Not sure if the course books are the same throughout the years but the page number is 10 in computer book A, table 4.2.

    Don't get what it is saying in the top line:confused:
  19. DFranklin's Avatar
    19 29-06-2012  16:09
    • TSR Royalty
    • Location: London
    • Posts: 18,046
    Re: Linear second-order recurrence sequence
    (Original post by SubAtomic)
    Hi, not quite sure what my book is saying here.

    I have a table, Coefficients p and q, Initial values a and b, and

    Apparent pattern in U^2_n+U^2_{n+1}

    Both coefficients have value 1, Initial values a=0 and b=1.

    So this is what the book says under the 'apparent pattern' section,

    it is every other term of U_n , starting with U_3

    Will post some screen shots of what mathcad shows. I don't get it, what does it mean it is every other term of U_n , starting with U_3.
    What are U_3, U_5, U_7, U_9, ...? Compare with the values for U^2_n+U^2_{n+1}.
  20. SubAtomic's Avatar
    20 29-06-2012  16:19
    • Exalted and Worshipped Member
    • Posts: 1,316
    Re: Linear second-order recurrence sequence
    (Original post by DFranklin)
    What are U_3, U_5, U_7, U_9, ...? Compare with the values for U^2_n+U^2_{n+1}.
    Can see that U_{2n+1} = U_n^2+U_{n+1}^2

    Just not too sure on the wording every other term
Sign in to Reply
Search Thread
Advanced Search
Share this discussion:  
Useful resources

Articles:

Study Help rules and posting guidelinesStudy Help Member of the Month nominationsGuide to MathematicsMathematics resourcesMathematics websitesMathematics revision notes in the TSR wikiCambridge Assessment admissions tests (including STEP)How to use LaTeXCareers in Mathematics

Useful Dates:

Quick Link:

Unanswered Maths Threads

Groups associated with this forum:

View associated groups
Article updates
Moderators

We have a brilliant team of more than 60 volunteers looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is moderated by:

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

Shortcuts

Get Started

TSR Group

Using TSR

Info

Connect with TSR

Reputation gems:
The Reputation gems seen here indicate how well reputed the user is, red gem indicate negative reputation and green indicates a good rep.
Post rating score:
These scores show if a post has been positively or negatively rated by our members.