Results 1 to 8 of 8

Thread: 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:

    $\displaystyle a) a_n = n + (-1)^{n} $
    $\displaystyle 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
    5
    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:

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

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

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

    So:

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

    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; Jun 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
    5
    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:

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

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

    $\displaystyle b_n=Aa_{n-1}+Ba_{n-2}$

    then:

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

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

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

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

    $\displaystyle b_n=a_n+2,$

    so:

    $\displaystyle
    a_n=b_n-2=2a_{n-1}-a_{n-2}
    $

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    12,028
    Thanks
    848
    Hello, robocop_911!

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

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


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


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



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

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


    Each term is: the preceding term, plus twice $\displaystyle n.$


    The recurrence is: . $\displaystyle 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
    5
    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:

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

    so:

    $\displaystyle 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 . . .

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


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


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



    We have:

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


    Each term is: the preceding term, plus twice $\displaystyle n.$


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

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

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

    a) $\displaystyle a_n = 5a_{n-1},\, a_1 = 5 $
    b) $\displaystyle a_n = na_{n-1}, \, a_1 = 1 $
    c) $\displaystyle 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
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by robocop_911 View Post
    Can't we just do $\displaystyle a_n - a_{n-1} = n^2+n - [ (n-1)^2 + (n-1) ] $
    i.e. subtract $\displaystyle a_n $ by $\displaystyle a_{n-1} $ we get the answer easily!
    But subtracting doesn't seem to work for say...
    a) $\displaystyle a_n = 5^n $
    b) $\displaystyle a_n = n! $
    c) $\displaystyle a_n = 3 $

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

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

    The only thing I can do for b) is by a similar division process but I get
    $\displaystyle 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: Jun 7th 2009, 04:14 PM
  2. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM
  3. Replies: 3
    Last Post: Feb 10th 2009, 03:51 AM
  4. recurrence relations
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Dec 10th 2008, 09:21 AM
  5. recurrence relations help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 19th 2008, 09:08 PM

Search Tags


/mathhelpforum @mathhelpforum