Results 1 to 4 of 4
Like Tree2Thanks
  • 2 Post By chiro

Math Help - Recurrence equations

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Ukraine
    Posts
    43

    Recurrence equations

    Hi.

    Could you help me solve these equations? I know how to solve recurrence equations with only [tex]a_k[\tex] and scalars in, and sometimes I can also guess the formula and then prove it by induction. But I have no idea how to go about solving these:


    1) a_{n}= \frac{ a_{n-1} ^{3} }{ a_{n-2} ^{2} } |||a_1=1, a_2=2

    2) a_n=2 \frac{n-1}{n}a_{n-1}+ \frac{1}{n}||| a_1=1

    3) a_n=5a_{n-1}-6a_{n-2}+4n-3 |||a_1=1, a_2=2

    4) a_n=5a_{n-1}-6a_{n-2}+3^n |||a_1=1, a_2=2

    5) a_n=5a_{n-1}-6a_{n-2}+n3^n |||a_1=1, a_2=2

    6) a_n=5a_{n-1}-6a_{n-2}+n^2 2^n |||a_1=1, a_2=2

    7) a_n=5a_{n-1}-6a_{n-2}+(n^2+1)3^n |||a_1=1, a_2=2

    And two problems:

    1)Find the number of strings length n consisting of numbers 0,1,2 where the following bits differ at most 1. What I mean is that such strins should look like that: 00000000111111222222222111111100000001111110000000 011111000001111122222111
    I've tried to find a recurrence pattern(if we begin with 0, then after the 0s we can only put 1s, but after 1s there can be 0s or 2s, but then after 0s and 2s there can be only 1s and there we go again) but I have no idea how to write such a recurrence since there can be any number of 1s,2s 0s used.

    2) similar, only this time we form bit strings using numbers 0, 1, 2, 3 and we need to find the number of strings in which 0 and 1 are not next to each other.

    Please help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Recurrence equations

    Hey wilhelm.

    You should show us everything you have tried and any brainstorming you have had for these problems to get specific and more importantly, useful feedback.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Ukraine
    Posts
    43

    Re: Recurrence equations

    Well, I have already solved the 1st and 2nd equations, using b_n=na_n and b_n=a_n=pn=q but I do not know what to do to "get rid of" 3^n or ....3^n. Putting -3^n in b_n doesn't help. What should I use. As to the first text problem, I have already written what I've tried doing. I'd be really grateful for some hint on solving these problems or maybe you could recommend a good book in which recurrence equations are nicely explained.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    Re: Recurrence equations

    Generally the way to solve general recurrence equations is to expand the relation by getting a_n in terms of an expression with only n's in them (usually a series, a multiplication, or something like that) and then classify the series in a way that gives a solution.

    This is how to solve the general case of recurrence relations and what mathematicians try and do is find a pattern for n terms where any simplification that can be done is done and any that isn't is just left in the best simplification form.

    This is the general case, but I did find a PDF that covers some specifics that include the classes of problems you have:

    http://rutherglen.science.mq.edu.au/...older/dm16.pdf
    Thanks from MarkFL and wilhelm
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Solving Recurrence Equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 20th 2012, 04:42 AM
  2. how to merge system of recurrence equations
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2011, 02:01 PM
  3. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  4. recurrence
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 8th 2009, 03:46 PM
  5. recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2009, 10:53 PM

Search Tags


/mathhelpforum @mathhelpforum