# Recurrence relation with variable $x$ in the denominator.

A recurrence is defined such that $$f_n(x)=f_1(f_{(n-1)}(x)); x\ge2$$

$f_1(x)$ is defined as

$$f_1(x)= \frac 23 -\frac 3{3x+1}$$

How can I find the values of $x$ for which the following holds true? $$f_{1001}(x)= x-3$$

I was not able to deduce any kind of pattern in the above recurrence. I did try to find a a pattern by finding $f_2$ and $f_3$ but I could not make out any generating function. How should I proceed?

• Normally recurrences like this are carefully constructed so they cycle. If you compute a few terms you will come back where you started, then you can reduce the number $1001$ modulo the cycle length. That is the case here, as Larry Lee proves and the cycle is $3$. May 16, 2017 at 4:45

Notice that $$f_2(x) = \frac{2}{3}-\frac{3}{3\cdot\left(\frac{2}{3}-\frac{3}{3x+1}\right)+1} = \frac{2}{3}-\frac{3x+1}{3x-2}$$ $$f_3(x) = \frac{2}{3}-\frac{3}{3\cdot\left(\frac{2}{3}-\frac{3x+1}{3x-2}\right)+1} = \frac{2}{3}+\frac{3x-2}{3}$$ $$f_4(x) = \frac{2}{3}-\frac{3}{3\cdot\left(\frac{2}{3}+\frac{3x-2}{3}\right)+1} = \frac{2}{3}-\frac{3}{3x+1}$$ This implies $f_4(x)=f_1(x)$. So we see that this is a cycle of $3$, meaning $$x-3=f_{1001}(x)=f_{998}(x)=\ ...\ =f_2(x)= \frac{2}{3}-\frac{3x+1}{3x-2}\implies x = \frac{5}{3}$$
• You could actually save the last step of calculations by noting that $f_3(x)=\cfrac{2}{3}+\cfrac{3x-2}{3}=x\,$, so $f_4(x)=f_1(f_3(x))=f_1(x)\,$. I don't think that step is transcribed right, anyway.
$$f_n + \frac{1}{3} = 1 - \frac{1}{f_{n-1}+\cfrac{\;\;1\;\;}{3}}$$
That means that $\;g_n=f_n+\cfrac{1}{3}\;$ satisfies $\;g_n = 1 - \cfrac{1}{g_{n-1}}\;$ and the cycle of $\;g(x)=1-\cfrac{1}{x}\,$ $\,\to \;(g \circ g)(x) = \cfrac{1}{1-x}\,$ $\,\to \;(g \circ g \circ g)(x)=x\,$ is among the better known ones.