1. Not finding help here? Sign up for a free 30min 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!

Sequence recursion formula

  1. Sep 14, 2014 #1
    Oddly enough, I don't remember doing a problem like. I have had a problem where I've been given the explicit formula and then asked to use induction to prove that it's correct.

    I think that I'm supposed to back-substitute sn into the recursion formula and go from there.
     
  2. jcsd
  3. Sep 15, 2014 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    It's not clear to me whether in your present problem you are given the explicit formula and asked to show it is correct, or whether it is the problem as quoted in your post. If the latter, what do you think you are back-substituting in?
     
  4. Sep 15, 2014 #3

    Mentallic

    User Avatar
    Homework Helper

    The OP is saying that he's solved problems where he's given an explicit formula and used induction to prove it is correct, but hasn't attempted a problem like the one in which he quoted.

    At least, that's what I think :smile:

    Start by figuring out what [itex]s_1,s_2,s_3,s_4[/itex] are, but don't substitute the value of [itex]s_{n-1}[/itex] in when figuring out [itex]s_n[/itex] and don't simplify the expression at all. Then start with [itex]s_4[/itex] and begin by substituting [itex]s_3[/itex] in, then [itex]s_2[/itex] etc. Do you notice a pattern?
     
  5. Sep 15, 2014 #4
    Yes, currently, the full problem is find the explicit formula, prove using induction, and then determine if it converges. I can do the last two parts; I'm just not sure how to get started. I figured that I could list the first few terms in the sequence and try to find a pattern, but I wasn't sure if there was a better, less brute forth method. Heh.

    Eh. It looks like [itex]\frac{n!}{2n}[/itex]
     
    Last edited: Sep 15, 2014
  6. Sep 15, 2014 #5

    Mentallic

    User Avatar
    Homework Helper

    I can't think of any simpler methods for your problem than plugging and finding the pattern, because the pattern is easy to notice.

    However, if you have to find an explicit formula for more complicated recurrences, then you should check out generating functions:

    http://faculty.tru.ca/smcguinness/M270F11/M270F11notes3.pdf

    No, it can't be [itex]\frac{n!}{2n}[/itex] because testing for n=1, we're already given that [itex]s_1=1[/itex] but [itex]\frac{n!}{2n}=\frac{1!}{2\cdot 1}=\frac{1}{2}[/itex].

    Could you write out what [itex]s_2[/itex] is in terms of [itex]s_1[/itex], then [itex]s_3[/itex] in terms of [itex]s_2[/itex]?
     
  7. Sep 15, 2014 #6
    Oops. You're right. Let me look at it again. I forgot to test for s1.
     
  8. Sep 15, 2014 #7
    s1 = 1
    s2 = [itex]\frac{2}{2}[/itex]s1
    s3 = [itex]\frac{3}{4}[/itex]s2
    s4 = [itex]\frac{4}{6}[/itex]s3
    s5 = [itex]\frac{5}{8}[/itex]s4
     
  9. Sep 15, 2014 #8

    Mentallic

    User Avatar
    Homework Helper

    Ok good, but now do it without equating 2*n in the denominator, just leave it as 2*3 for example.

    Now, starting at s4 (you can start at s5 but s4 should be far enough up the chain to notice the pattern), begin by substituting the value of s3 in terms of s2 so you then have s4 in terms of s2. Then substitute again so it's in terms of s1, all the while not simplifying at all. Do you notice any patterns? Could you figure out what sn would look like in terms of s1?
     
  10. Sep 15, 2014 #9
    (sn) = [itex]n(\frac{1}{2})[/itex]n-1
     
  11. Sep 16, 2014 #10

    Mentallic

    User Avatar
    Homework Helper

    That's it!
     
  12. Sep 16, 2014 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Sorry I couldn't get back to this earlier.
    Fwiw, there are some more methodical approaches than pattern spotting. On this one, I would first note that it is homogeneous, i.e. Given any two solutions to the recursion formula, any linear combination is also a solution.
    Next, look at the asymptotic behaviour of the formula. For large n, it is roughly sn+1 = sn/2, suggesting the substitution sn = un2-n. That yields ##\frac{u_{n+1}}{n+1}=\frac{u_n}{n}##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Sequence recursion formula
  1. Recursive formulae (Replies: 14)

Loading...