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!

Recursive formulae

  1. Mar 6, 2008 #1
    [SOLVED] Recursive formulae

    1. The problem statement, all variables and given/known data
    Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid.

    a) f(0) = 1, f(n) = -f(n – 1) for n >= 1

    3. The attempt at a solution
    f(1) = -f(1 – 1) = -f(0) = -1
    f(2) = -f(2 – 1) = -f(1) = 1
    f(3) = -f(3 – 1) = -f(2) = -1

    I can see that it is a valid recursive definition.
    Why is it asking me to find a formula for f(n), when we were given it (= -f(n-1))?
    Are they asking for a nonrecursive formula that also applies?

    In this case, it would be f(n) = (-1)^n.
    Is this what they want?
     
  2. jcsd
  3. Mar 6, 2008 #2
    Yes. It is.
     
  4. Mar 6, 2008 #3
    How would I "prove" these to be equivalent?
     
  5. Mar 6, 2008 #4
    You mean prove that f(n) = (-1)^n? Use induction.
     
  6. Mar 7, 2008 #5
    One of the questions I'm now facing, I can't answer with one formulae. f(2k) = 0, regardless of k, and f(2k+1) keeps doubling. I could possibly use two formulae, one for even, one for odd, but is this what I am to do, or is this considered a "not well defined" function?
     
  7. Mar 7, 2008 #6
    Consider both even and odd cases as you have already pointed out. Ask yourself this: If it isn't well defined, for what values of the argument is it not well defined?
     
  8. Mar 7, 2008 #7
    My book says,
    Unsure about "well" defined, but the formula is "defined" for all positive integers.
    For reference, it's:
    f(0) = 1, f(1) = 0, f(2) = 2, f(n) = 2f(n – 3) for n >= 3

    From which, you see at pattern of:
    1, 0, 2, 0, 4, 0, 8, 0, 16, 0, 32, 0, etc.
     
  9. Mar 7, 2008 #8
    Made a mistake.
    It actually goes:
    Code (Text):
       n = 0, 1, 2, 3, 4, 5, 6
    f(n) = 1, 0, 2, 2, 0, 4, 8
     
    This makes it even harder to make a formula for.
     
  10. Mar 7, 2008 #9

    Ben Niehoff

    User Avatar
    Science Advisor
    Gold Member

    There is a standard method of solving recurrence relations. Is your course not teaching it? It works like this:

    Try a solution of the form

    [tex]F(n) = r^n[/tex]

    where r is some number yet to be determined. Now, plug this into your recurrence relation, and you will get an algebraic equation for r. For example, suppose you have the Fibonacci sequence:

    [tex]F(n) = F(n-1) + F(n-2)[/tex]

    Plugging in [itex]F(n) = r^n[/itex], we get

    [tex]r^n = r^{n-1} + r^{n-2}[/itex]

    Now, simply divide both sides by [itex]r^{n-2}[/itex] and move everything to the left side to get a quadratic equation in r:

    [tex]r^2 - r - 1 = 0[/tex]

    Solving this for r, you obtain

    [tex]r = \frac{1\pm\sqrt5}2[/tex]

    (note: if you take the plus sign, you get the Golden Ratio!). Now, since you have two different solutions, you can try a linear combination of them:

    [tex]F(n) = Ar_1^n + Br_2^n[/tex]

    In order to find A and B, you use your initial values:

    [tex]F(0) = 1[/tex]
    [tex]F(1) = 1[/tex]

    which will lead to a system of two linear equations to solve for A and B.
     
  11. Mar 7, 2008 #10

    Ben Niehoff

    User Avatar
    Science Advisor
    Gold Member

    Note that if you DID have a sequence like

    [tex]1, 0, 2, 0, 4, 0, 8, ...[/tex]

    then you can proceed by noting that this is a sum of two sequences:

    [tex]\frac12, \frac{\sqrt2}2, 1, \frac{\sqrt8}2, 2, \frac{\sqrt{32}}2, 4, ...[/tex]
    [tex]\frac12, -\frac{\sqrt2}2, 1, -\frac{\sqrt8}2, 2, -\frac{\sqrt{32}}2, 4, ...[/tex]

    and then you can write down the answer as

    [tex]\frac12\left[(\sqrt2)^n + (-\sqrt2)^n\right][/tex]
     
  12. Mar 8, 2008 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Divide it into three cases: n= 3k, n= 3k+1, n= 3k+ 2.
     
  13. Mar 8, 2008 #12
    But the thing is, I only need to do this work if it is "well defined". But, all of the questions seem "well defined", which throws me off =/

    a) f(0) = 1, f(n) = -f(n – 1) for n >= 1
    b) f(0) = 1, f(1) = 0, f(2) = 2, f(n) = 2f(n – 3) for n >= 3
    c) f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n >= 2
    d) f(0) = 0, f(1) = 1, f(n) = 2f(n – 1) for n >= 1
    e) f(0) = 2, f(n) = f(n – 1) if n is odd and n >= 1 and f(n) = 2f(n – 2) if n >= 2

    They all seem to be valid to me...
    Should I just ignore the "well defined" part and do it anyway?
     
  14. Mar 8, 2008 #13

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, you could go ahead and try to find a "closed form" formula for f(n). If you can then the recursive formula must be "well defined"!

    In (c), you have "f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n >= 2". What is f(2)? How would you find f(3)?
     
    Last edited: Mar 8, 2008
  15. Mar 8, 2008 #14
    f(2) = 2f(3), but we don't have f(3), so we switch things a bit.
    f(n) = 2f(n+1)
    f(n)/2 = f(n+1)
    Which I believe would be the same as f(n-1)/2 = f(n)

    Plug in 2 for n, and you get...
    f(2) = f(1)/2 = 1/2
    For n=3, f(3) = f(2)/2 = 1/4

    So a formula for this could be something similar to [tex]f(0) = 0, f(n) = \frac{1}{2^{n-1}}[/tex] for n [itex]\geq 1.[/itex].
     
    Last edited: Mar 8, 2008
  16. Mar 8, 2008 #15

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Very nice. But f(n)= 2f(n+1) is only defined for n>= 2 so that f(n-1)= 2f(n) and then f(n)= (1/2)f(n-1) is only defined for n-1>= 2 or n>= 3.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Recursive formulae
Loading...