Results 1 to 8 of 8

Math Help - recurrence relations of given sequences

  1. #1
    Member
    Joined
    May 2008
    Posts
    94

    recurrence relations of given sequences

    Hi there,

    Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

    e.g. take the sequences:

     a) a_n = n + (-1)^{n}
     b) a_n = n^{2} + n

    What are the recurrence relations of the above examples?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by robocop_911 View Post
    Hi there,

    Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

    e.g. take the sequences:

     a) a_n = n + (-1)^{n}
     b) a_n = n^{2} + n

    What are the recurrence relations of the above examples?
    For the first look at a_{n-1},

    a_{n-1}=(n-1)+(-1)^{n-1}=n-1+(-1)^{n-1}=a_n-(-1)^n+(-1)^{n-1}-1 =a_n+2(-1)^{n-1}-1

    So:

     <br />
a_n=a_{n-1}-2(-1)^{n-1}+1=a_{n-1}+2(-1)^{n}+1<br />

    Which is not entirly satisfactory as we still hane n appearing other than as a subscript on the right, I will look at it again when I get the chance.

    RonL
    Last edited by CaptainBlack; June 4th 2008 at 03:32 AM. Reason: correct errors
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by robocop_911 View Post
    Hi there,

    Can anybody give me a brief tutorial on how to find "recurrence relation" of any given sequence...

    e.g. take the sequences:

     a) a_n = n + (-1)^{n}
     b) a_n = n^{2} + n

    What are the recurrence relations of the above examples?
    For the second as a_n is a quadratic in n if we are looking for a linear recurence we know that this must involve two earlier terms in the sequence, so put:

    b_n=Aa_{n-1}+Ba_{n-2}

    then:

    b_n=A[(n-1)^2+(n-1)]+B[(n-2)^2+(n-2)]

    ... = A[n^2-2n+1+n-1]+B[n^2-4n+4+n-2]

    ... =A[a_n-2n]+B[a_n-4n-2]=(A+B)a_n + n(-2A-4B) -2B

    Now let A=2,\ B=-1, this becomes:

    b_n=a_n+2,

    so:

     <br />
a_n=b_n-2=2a_{n-1}-a_{n-2}<br />

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,719
    Thanks
    635
    Hello, robocop_911!

    1)\;\; a_n \:= \:n + (-1)^n
    Crank out the first few terms . . .

    . . \begin{array}{ccccccc}a_1 &=& 1 + (-1)^1 &=& 0 \\<br />
& & & & \rangle & +3 \\<br />
a_2 &=& 2 + (-1)^2 &=& 3 \\<br />
& & & & \rangle & -1 \\<br />
a_3 &=& 3 + (-1)^3 &=& 2 \\<br />
& & & & \rangle & +3 \\<br />
a_4 &=& 4 + (-1)^4 &=& 5 \\<br />
& & & & \rangle & -1 \\<br />
a_5 &=& 5 + (-1)^5 &=& 4 \\<br />
& & & & \rangle & +3 \\<br />
a_6 &=& 6 + (-1)^6 &=& 7 \end{array}


    We are alternately "adding 3 to" and "subtracting 1 from" the preceding term.


    The recurrence is: . a_n \;=\;a_{n-1} + 1 + 2(-1)^n



     2)\;\; a_n \:= \:n^2 + n
    We have:

    . . \begin{array}{ccccccccc}<br />
a_1 &=& 1^2+1 &=& 2 \\<br />
& & & & \rangle & +4 &=& 2(2)  \\<br />
a_2 &=& 2^2+2 &=& 6 \\<br />
& & & & \rangle & +6 &=& 2(3)  \\<br />
a_3 &=& 3^2 + 3 &=& 12 \\<br />
& & & & \rangle & +8 &=& 2(4)  \\<br />
a_4 &=& 4^2 + 4 &=& 20 \\<br />
& & & & \rangle & +10 &=& 2(5) \\<br />
a_5 &=& 5^2 + 5 &=& 30\end{array}


    Each term is: the preceding term, plus twice n.


    The recurrence is: . a_n \;=\;a_{n-1} + 2n

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Which is not entirly satisfactory as we still hane n appearing other than as a subscript on the right, I will look at it again when I get the chance.

    RonL
    OK here goes:

    a_{n-2}=(n-2)+(-1)^{n-2}=(n-2)+(-1)^n=a_n-2

    so:

    a_n=a_{n-2}+2

    and we need two terms for our initial conditions.

    RonL
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    May 2008
    Posts
    94
    Quote Originally Posted by Soroban View Post
    Hello, robocop_911!

    Crank out the first few terms . . .

    . . \begin{array}{ccccccc}a_1 &=& 1 + (-1)^1 &=& 0 \\<br />
& & & & \rangle & +3 \\<br />
a_2 &=& 2 + (-1)^2 &=& 3 \\<br />
& & & & \rangle & -1 \\<br />
a_3 &=& 3 + (-1)^3 &=& 2 \\<br />
& & & & \rangle & +3 \\<br />
a_4 &=& 4 + (-1)^4 &=& 5 \\<br />
& & & & \rangle & -1 \\<br />
a_5 &=& 5 + (-1)^5 &=& 4 \\<br />
& & & & \rangle & +3 \\<br />
a_6 &=& 6 + (-1)^6 &=& 7 \end{array}


    We are alternately "adding 3 to" and "subtracting 1 from" the preceding term.


    The recurrence is: . a_n \;=\;a_{n-1} + 1 + 2(-1)^n



    We have:

    . . \begin{array}{ccccccccc}<br />
a_1 &=& 1^2+1 &=& 2 \\<br />
& & & & \rangle & +4 &=& 2(2)  \\<br />
a_2 &=& 2^2+2 &=& 6 \\<br />
& & & & \rangle & +6 &=& 2(3)  \\<br />
a_3 &=& 3^2 + 3 &=& 12 \\<br />
& & & & \rangle & +8 &=& 2(4)  \\<br />
a_4 &=& 4^2 + 4 &=& 20 \\<br />
& & & & \rangle & +10 &=& 2(5) \\<br />
a_5 &=& 5^2 + 5 &=& 30\end{array}


    Each term is: the preceding term, plus twice n.


    The recurrence is: . a_n \;=\;a_{n-1} + 2n

    Can't we just do  a_n - a_{n-1} = n^2+n - [ (n-1)^2 + (n-1) ]
    i.e. subtract  a_n by  a_{n-1} we get the answer easily!
    But subtracting doesn't seem to work for say...
    a)  a_n = 5^n
    b)  a_n = n!
    c)  a_n = 3

    What to do then?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by robocop_911 View Post
    i.e. subtract  a_n by  a_{n-1} we get the answer easily!
    But subtracting doesn't seem to work for say...
    a)  a_n = 5^n
    b)  a_n = n!
    c)  a_n = 3

    What to do then?
    Its a little different, but the idea is the same... try multiplication!

    a)  a_n = 5a_{n-1},\, a_1 = 5
    b)  a_n = na_{n-1}, \, a_1 = 1
    c)  a_n = a_{n-1}, \, a_1 = 3
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,907
    Thanks
    329
    Awards
    1
    Quote Originally Posted by robocop_911 View Post
    Can't we just do  a_n - a_{n-1} = n^2+n - [ (n-1)^2 + (n-1) ]
    i.e. subtract  a_n by  a_{n-1} we get the answer easily!
    But subtracting doesn't seem to work for say...
    a)  a_n = 5^n
    b)  a_n = n!
    c)  a_n = 3

    What to do then?
    Well, c) is easy since it's a constant.

    a) you can do by division:
    \frac{a_{n}}{a_{n - 1}} = \frac{5^n}{5^{n- 1}} = 5
    so
    a_n = 5a_{n - 1}

    The only thing I can do for b) is by a similar division process but I get
    a_n = n \cdot a_{n - 1}
    which is still in terms of n. I doubt this one can be done in another way. (Unless you want to define the "inverse gamma function." Possible I suppose, but I've never seen it.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Recurrence Relations
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 7th 2009, 04:14 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM
  3. Replies: 3
    Last Post: February 10th 2009, 03:51 AM
  4. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: December 10th 2008, 09:21 AM
  5. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 19th 2008, 09:08 PM

Search Tags


/mathhelpforum @mathhelpforum