Disclaimer: these are my personal solutions; they have not been reviewed, so be careful relying on them as there might be errors. Some competitions may have official solutions from the contest publishers which you may wish to refer to instead if you’re looking for verified solutions.
Problem 6
Given the linear fractional transformation of $x$ into $\displaystyle{ f_1(x) = \frac{2x - 1}{x + 1} }$, define $f_{n + 1}(x) = f_1(f_n(x))$ for $n = 1, 2, 3, …$. It can be shown that $f_{35} = f_5$. Determine $A$, $B$, $C$, and $D$ so that $\displaystyle{ f_{28}(x) = \frac{Ax + B}{Cx + D} }$.
Hints
Hint #1
Sure, you can compute $f_{28}$ manually, but maybe there’s an easier and faster way?
Hint #2
Can you use $f_{35} = f_5$ somehow to limit the amount of computation you need to do?
Hint #3
Work backwards from $f_{35}$ using $f_{35} = f_5$ until you can reach $f_{28}$.
Solution
Open to see the solution; try solving it first or see the hints above!
Per the problem statement, we know that:
$$ f_{n+1}(x) = f_1(f_n(x)) $$
which tells us that $f_n(x)$ is equivalent to $n$ successive applications of $f_1$:
$$ f_n(x) = \underbrace{f_1(f_1(… f_1(x) …))}_{\text{$f_1$ applied $n$ times to $x$}} $$
Note: below, for notational simplicity, we will replace $f_n(x)$ with $f_n$ to eliminate the often-appearing $(x)$ term, which will make it easier to read. We will bring it back when necessary.
What we need to find is $f_{28}$, so we could just apply $f_1(x)$ recursively $28$ times, but that seems tedious and not a good use of our time (and especially, if we were doing this in a timed math contest, as VTRMC is, we would not have enough time for the other problems), so we need to find a shortcut here.
Since the problem statement also tells us that $f_{35} = f_5$, we see that there’s a cycle, which implies that we can align these functions forward and backward to find other equivalences:
$$ \begin{align*} & \vdots \\ f_{36} & = f_6 \\ f_{35} & = f_5 & \text{given in problem statement} \\ f_{34} & = f_4 \\ & \vdots \\ \end{align*} $$Why can we assume that $f_{35} = f_5$ implies that functions align forward and backward? Let’s look at the forward computation:
$$ \begin{align*} f_{n} & = f_{k} \\ f_1(f_{n}) & = f_1(f_k) & \text{replace each side $s$ with $f_1(s)$} \\ f_{n+1} & = f_{k+1} \\ \end{align*} $$We can similarly run this backwards:
$$ \begin{align*} f_{n} & = f_{k} \\ f_1(f_{n-1}) & = f_1(f_{k-1}) & \text{from the definition above} \\ f_{n-1} & = f_{k-1} & \text{remove $f_1$ application from each side (see note below)} \\ \end{align*} $$Note: why can we remove the $f_1$ application from each side above? Because $f_1$ is injective, which means that if $f_1(x) = f_1(y)$, then $x = y$ for all $x, y$.
Why is $f_1$ injective? Let’s take $f_1(x) = \dfrac{2x - 1}{x + 1}$ and consider $f_1(a)$ and $f_1(b)$ and see if that implies that $a = b$:
$$ \begin{align*} f_1(a) & = f_1(b) \\ \frac{2a - 1}{a + 1} & = \frac{2b - 1}{b + 1} & \quad \text{expand $f_1$} \\ (2a - 1)(b + 1) & = (2b - 1)(a + 1) & \quad \text{cross-multiply} \\ 2ab - b + 2a - 1 & = 2ab - a + 2b - 1 & \quad \text{expand terms} \\ -b + 2a & = -a + 2b & \quad \text{subtract $2ab - 1$} \\ 3a & = 3b & \quad \text{combine like terms} \\ a & = b & \quad \text{divide by $3$} \\ \end{align*} $$We’ve shown that $f_1(a) = f_1(b) \implies a = b$ for all $a, b$.
Therefore, we can run $f_1$ applications backward from $f_{35} = f_5$ to find other equivalences.
Since we need to find the definition of $f_{28}$, let’s run the equivalences backward enough to find what it’s equivalent to:
$$ \begin{align*} f_{35} & = f_5 & \quad \text{given in problem statement} \\ f_{34} & = f_4 \\ f_{33} & = f_3 \\ f_{32} & = f_2 \\ f_{31} & = f_1 \\ f_{30} & = \; ? \\ f_{29} & = \; ? \\ f_{28} & = \; ? & \quad \text{what we're trying to compute} \\ \end{align*} $$However, $f_n$ is only defined for $n \ge 1$, so we have to stop at $f_{31} = f_1$, and then we can compute the rest of the functions iteratively.
First, note that since $f_{31}(x) = f_1(f_{30}(x)) = f_1(x)$, we have $f_{30}(x) = x$.
Second, we know that $f_{30}(x) = f_1(f_{29}(x)) = x$, so let’s compute $f_{29}$:
$$ \begin{align*} f_{30}(x) & = f_1(f_{29}(x)) & \quad \text{from problem statement} \\ f_{30} & = f_1(f_{29}) & \quad \text{simplify notation per above} \\ x & = f_1(f_{29}) & \quad \text{substitute $f_{30}$ per above} \\ x & = \frac{2 f_{29} - 1}{f_{29} + 1} & \quad \text{evaluate $f_1$} \\ x \left( f_{29} + 1 \right) & = 2 f_{29} - 1 & \quad \text{} \\ x \cdot f_{29} + x & = 2 f_{29} - 1 & \quad \text{distribute $x$} \\ x \cdot f_{29} - 2 f_{29} & = -x - 1 & \quad \text{group like terms} \\ f_{29} \cdot (x - 2) & = -x - 1 & \quad \text{factor out $f_{29}$} \\ f_{29} & = \frac{-x - 1}{x - 2} & \quad \text{solve for $f_{29}$} \\ f_{29} & = \frac{x + 1}{2 - x} & \quad \text{simplify signs} \\ \end{align*} $$Finally, let’s compute $f_{28}$:
$$ \begin{align*} f_{29} & = f_1(f_{28}) & \quad \text{from problem statement} \\ \frac{x + 1}{2 - x} & = f_1(f_{28}) & \quad \text{substitute definition of $f_{29}$} \\ \frac{x + 1}{2 - x} & = \frac{2 f_{28} - 1}{f_{28} + 1} & \quad \text{evaluate $f_1$} \\ (x + 1)(f_{28} + 1) & = (2 f_{28} - 1)(2 - x) & \quad \text{cross-multiply} \\ x \cdot f_{28} + x + f_{28} + 1 & = 4 \cdot f_{28} - 2x \cdot f_{28} -2 + x & \quad \text{expand} \\ 3x \cdot f_{28} - 3 f_{28} & = x - x - 2 - 1 = - 3 & \quad \text{combine like terms} \\ x \cdot f_{28} - f_{28} & = -1 & \quad \text{divide by $3$} \\ f_{28} (x - 1) & = -1 & \quad \text{factor out $f_{28}$} \\ f_{28} & = \frac{-1}{x - 1} & \quad \text{solve for $f_{28}$, solution $A$} \\ f_{28} & = \frac{1}{1 - x} & \quad \text{simplify signs, solution $B$} \\ \end{align*} $$The problem asks us to find $A$, $B$, $C$, and $D$ to satisfy $$ f_{28}(x) = \frac{Ax + B}{Cx + D} $$
However, as we saw above, there are actually multiple solutions to this problem, since we can multiply the numerator and denominator by any real number to obtain another valid solution.
$$ \begin{align*} f_{28}(x) & = \frac{Ax + B}{Cx + D} & \quad \text{from problem statement} \\ & = \frac{1}{1 - x} & \quad \text{from solution $B$ above} \\ & = \frac{0x + 1}{-x + 1} & \quad \text{reorganize to match pattern} \\ \end{align*} $$Therefore, $ \boxed{A = 0; \quad B = 1; \quad C = -1; \quad D = 1} \quad$ is one valid solution.
Another solution is:
$$ \begin{align*} f_{28}(x) & = \frac{Ax + B}{Cx + D} & \quad \text{from problem statement} \\ & = \frac{-1}{x - 1} & \quad \text{from solution $A$ above} \\ & = \frac{0x - 1}{x - 1} & \quad \text{reorganize to match pattern} \\ \end{align*} $$Here, the solution is: $ \boxed{A = 0; \quad B = -1; \quad C = 1; \quad D = -1} \quad$ which can be obtained by multiplying the numbers in the above box by $-1$. $\quad \blacksquare$