Evaluating a recursive function

[Bashyboy]

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!

 

[D H]

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

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.

 

[Ray Vickson]

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!

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.

 

[pasmith]

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.

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...

 

[Ray Vickson]

I was hoping the OP could figure that out on his own.