1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recurrence Relations

  1. Mar 14, 2008 #1
    [SOLVED] Recurrence Relations

    1. The problem statement, all variables and given/known data
    I need to express this recursive statement as a nonrecursive formula, using the technique of itteration.

    [tex]a_n = (n+1)a_{n-1}[/tex]
    [tex]a_0 = 2[/tex]

    3. The attempt at a solution
    [tex]a_n = (n+1)a_{n-1}[/tex]
    [tex]a_n = (n+1)(n+1)a_{n-2} = (n+1)^{2}a_{n-2}[/tex]
    [tex]a_n = (n+1)(n+1)(n+1)a_{n-3} = (n+1)^{3}a_{n-3}[/tex]
    [tex]a_n = (n+1)^{n}a_{n-n}[/tex]
    [tex]a_n = 2(n+1)^{n}[/tex]

    I plugged both the recursive formula, and my answer, into MS-Excel, and they don't match up. They work for n = 0,1, but then my answer start getting larger than the recursive one.
  2. jcsd
  3. Mar 14, 2008 #2
    Here's the spreadsheet I'm using to check my answer.

    First column is n
    Second column is the recursive
    Third column is my proposed answer

    Attached Files:

  4. Mar 14, 2008 #3


    User Avatar
    Science Advisor
    Homework Helper

    Hi Goldenwind! :smile:

    With these recurrence questions, always start by working out what a_n+2 is in terms of a_n.

    Then a_n+3.

    By then, you should have a good idea of what is happening.

    So … what is happening? :smile:
  5. Mar 14, 2008 #4
    [tex]a_n = (n+1)a_{n-1}[/tex]

    Which is the same as
    [tex]\frac{a_{n+1}}{n+1} = a_{n}[/tex]

    [tex]\frac{a_{n+2}}{{(n+1)}^2} = a_{n}[/tex]

    [tex]\frac{a_{n+3}}{{(n+1)}^3} = a_{n}[/tex]

    I still don't see my mistake :(
    This is pretty much what I did above, only the other way around >.>
  6. Mar 14, 2008 #5


    User Avatar
    Science Advisor
    Homework Helper

    No no no … :frown:

    First, don't rearrange the formula - it's simplest as it is!

    Then … be careful!

    You should have [tex]a_{n+2}\,=\,(n+2)a_{n+1}\,=\,(n+2)(n+1)a_n\,.[/tex]

    So … the nonrecursive formula is … ? :smile:
  7. Mar 14, 2008 #6


    User Avatar
    Science Advisor

    I always start a problem involving any kind of sequence by working out a few values!

    [itex]a_1= (1+1)a_0= 2a_0[/itex]
    [itex]a_2= (2+1)a_1= 3a_1= 3(2)a_0[/itex]
    [itex]a_3= (3+1)a_2= 4a_2= 4(3)(2)a_0[/itex]
    [itex]a_4= (4+1)a_3= 5a_3= 5(4)(3)(2)a_0[/itex]

    Anything come to mind?
  8. Mar 14, 2008 #7
    [itex]a_n = 2(n+1)![/itex]
    ...is what it looks like to me.

    However, even if I know the formula, I need to demonstrate that this *is* the formula, via iteration.

    As in, I start out with [itex]a_n = (n+1)a_{n-1}[/itex], then replace [itex]a_{n-1}[/itex] with [itex]a_{n-1} = (n+1)a_{n-2}[/itex], then replace [itex]a_{n-2}[/itex] with [itex]a_{n-2} = (n+1)a_{n-3}[/itex], and so on, until I get to [itex]a_{n-n} = a_0[/itex], where I can simply sub in the given base value, as shown above.
  9. Mar 14, 2008 #8
    Yeah, I see my mistake... when I replaced n with n-1, or n-1 with n-2, I didn't change the (n+1) at all. Doing so would lead to the factorial, instead of [itex](n+1)^n[/itex].

    Thank you for your help :)
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Recurrence Relations
  1. Recurrence Relation (Replies: 1)

  2. Recurrence relations (Replies: 1)

  3. Recurrence Relations (Replies: 4)

  4. Recurrence relation (Replies: 2)

  5. Recurrence relation (Replies: 5)