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!

Evaluating a recursive function

  1. Sep 20, 2014 #1
    Hello everyone,

    Here is the problem:

    Let ##\displaystyle f_0() = \frac{1}{1-x}##, and ##f_n(x) = f_0(f_{n-1}(x))##, where ##n \in \mathbb{N}##. Evaluate ##f_{2014}(2014)##.

    I first sought after a pattern, and then tried to make a conjecture. Here is what I found:

    ##\displaystyle f_1(x) = f_0(f_(x)) = \frac{1}{1 - \frac{1}{x-1}} = \frac{1-x}{-x} = \frac{(f_0(x))^{-1}}{-x}##

    ##\displaystyle f_2(x) = f_0(f_1(x)) = \frac{1}{1- \left(\frac{(f_0(x))^{-1}}{-x} \right)} = \frac{x}{x + (f_0(x))^{-1}}##

    ##\displaystyle f_3(x) = f_0(f_2(x)) = \frac{1}{1 - \left(\frac{x}{x + (f_0(x))^{-1}} \right)} = \frac{ x + (f_0(x))^{-1} }{x + (f_0(x))^{-1} - x } = \frac{x + (f_0(x))^{-1} }{(f_0(x))^{-1}}##

    ##\displaystyle f_4(x) = f_0(f_3(x)) = \frac{1}{1 - \left(\frac{x + (f_0(x))^{-1} }{(f_0(x))^{-1} } \right)} = \frac{(f_0(x))^{-1}}{-x} = f_1(x)##

    ##f_5(x) = f_2(x)##

    ##f_6(x) = f_3(x)##

    So, after the functions ##f_1,~f_2,~f_3##, a pattern begins to emerge, and therefore these three functions are the base functions. The conjecture is that, if you begin with the ##j##-th function, the function will not repeat until the ##(j+3)##-th function.

    So, I need to figure out how to "reduce" the number 2014 to either 1,2, or 3 by repeatedly subtracting 3 from 2014 until I arrive at 1,2, or 3. Equivalently, I could repeatedly add 3 to 1,2, and 3, until I reached 2014, and then I would know which function ##f_{2014}## is equivalent to. But I am having difficulty figuring out exactly how to do this without actually doing the addition or subtraction. I know that multiplication of integers is defined in terms of addition; it is repeated addition. So, asking how many times I can add 3 to a number until I get 2014 is related to multiplication, which in turn is related to division, because division is defined in terms of multiplication.

    I hope you can help!
     
  2. jcsd
  3. Sep 20, 2014 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Try reducing your [itex]f_1(x)[/itex] a bit more. In particular, reduce that [itex]f_0(x)[/itex] term to something more basic. Do the same for [itex]f_2(x)[/itex] and then [itex]f_3(x)[/itex]. Done right, you should only operations involving numbers and the letter [itex]x[/itex] in the expressions for your [itex]f_n(x)[/itex].

    You should see one more pattern emerge in addition to what you've already seen. This should help you find the answer to your question.
     
  4. Sep 20, 2014 #3

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You can figure it out for yourself: when you subtract 3 once you get 2014 - 3. Two subtractions give you 2014 - 2*3. So, when perform n subtractions of 3 you get 2014 - 3*n. You want this to give you either 0, 1 or 2.
     
  5. Sep 20, 2014 #4

    pasmith

    User Avatar
    Homework Helper

    There are many ways to do this. Firstly you can calculate 2014/3 by long division to determine the remainder. Or you can use the trick that a number is divisible by 3 if its digits sum to a multiple of 3: 2 + 0 + 1 + 4 = 7, so 2 + 0 + 1 + 3 = 6...
     
  6. Sep 20, 2014 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I was hoping the OP could figure that out on his own.
     
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: Evaluating a recursive function
  1. Evaluating Functions (Replies: 6)

Loading...