Results 1 to 5 of 5

Math Help - Recurrence relation

  1. #1
    Newbie
    Joined
    Apr 2008
    Posts
    21

    Recurrence relation

    I've been given the following recurrence realtion:
    a_n_+_1 = a_n_-_1 + a_n_-_3  *a_n_-_4
    How many starting values are needed to be able to calculate the number series that solves the recurrence relation.

    The solution I've been given tells me I need 5 numbers, a_n to a_n_-_4
    of which 2 are not used in the above equation but needed to solve a_n_+_2

    I dont really understand how they arrive at this or why a_n_+_2 even is needed to be solved here.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,965
    Thanks
    1785
    Awards
    1

    Re: Recurrence relation

    Quote Originally Posted by dipsy34 View Post
    I've been given the following recurrence realtion:
    a_n_+_1 = a_n_-_1 + a_n_-_3  *a_n_-_4
    How many starting values are needed to be able to calculate the number series that solves the recurrence relation.

    The solution I've been given tells me I need 5 numbers, a_n to a_n_-_4
    of which 2 are not used in the above equation but needed to solve a_n_+_2
    You need to know a_0,~a_1,~a_2,~a_3,~\&~a_4.
    That is five values. Now we can find a_n for n\ge 5.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Recurrence relation

    Write numbers from 0 to, say, 10 in a row. The minimum value for n in the equation is 4 because there is an index n - 4. So, starting from n = 4 calculate the indices occurring in the right-hand side of the equation, i.e., n - 1, n - 3 and n - 4. If any of these numbers are not circled yet (and initially none of the numbers from 0 to 10 are circled), draw a circle around them and also write that number in a separate place. Finally, for the same value of n draw a circle around n + 1 (no need to write n + 1 separately). The newly circled numbers have to be provided to start the computation. Continue doing this for n = 5, 6, etc., and in the end see which numbers you have written in that separate place.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Apr 2008
    Posts
    21

    Re: Recurrence relation

    Quote Originally Posted by emakarov View Post
    Write numbers from 0 to, say, 10 in a row. The minimum value for n in the equation is 4 because there is an index n - 4. So, starting from n = 4 calculate the indices occurring in the right-hand side of the equation, i.e., n - 1, n - 3 and n - 4. If any of these numbers are not circled yet (and initially none of the numbers from 0 to 10 are circled), draw a circle around them and also write that number in a separate place. Finally, for the same value of n draw a circle around n + 1 (no need to write n + 1 separately). The newly circled numbers have to be provided to start the computation. Continue doing this for n = 5, 6, etc., and in the end see which numbers you have written in that separate place.
    Nifty little trick, many thanks!Easy to get an answer and to prove with induction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Aug 2011
    Posts
    127

    Re: Recurrence relation

    Just to add another tip here, though obscure: you only need one base value if you assume that the addition and multiplication are undefined when neither operand is present (in which case it is treated as "blank" in the same context as the non-existent variables), and when one operand is present but not the other, the remaining operand is unity for that function. The unity for multiplication is 1. The unity for addition is 0.

    Example (where "dne" means "does not exist"):
    a_0 = 1 (the only given...can start at any positive number, and the function will be increasing)
    a_1 = a_0 + dne * dne = a_0 + dne = a_0 + 0 = 1.
    a_2 = a_1 + dne * dne = a_1 + dne = a_1 + 0 = 1.
    a_3 = a_2 + a_0 * dne = a_2 + a_0 * 1 = a_2 + a_0 = 2.
    a_4 = a_3 + a_1 * a_0 = a_3 + 1 = 3.
    a_5 = a_4 + a_2 * a_1 = a_4 + 1 = 4.
    a_6 = a_5 + a_3 * a_2 = a_5 + 2 = 6.

    ...and so on. Note that the "dne" sticks around until you get past the first four cases.

    There are situations where this is a particularly useful approach, though I wouldn't normally assume this behavior is intended without being told it's allowed (here). This is how you handle empty sums and products in the general case, though.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 16th 2011, 12:27 AM
  2. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 18th 2010, 03:15 AM
  3. Recurrence Relation HELP
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 3rd 2009, 02:18 PM
  4. recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 15th 2009, 07:20 PM
  5. Recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2008, 09:02 AM

Search Tags


/mathhelpforum @mathhelpforum