1
$\begingroup$

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?

$\endgroup$
1
  • 3
    $\begingroup$ 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$. $\endgroup$ May 16, 2017 at 4:45

2 Answers 2

6
$\begingroup$

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}$$

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – dxiv
    May 16, 2017 at 5:49
  • 1
    $\begingroup$ Nice suggestion! Also, thanks for noticing the typo :) :) $\endgroup$
    – Lazy Lee
    May 16, 2017 at 6:16
2
$\begingroup$

(Too long for a comment.) The cyclicity alluded to in Ross Millikan's comment may be easier to recognize (and verify) if the recurrence relation is rewritten as:

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .