Back to problem set

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 xx into f1(x)=2x−1x+1\displaystyle{ f_1(x) = \frac{2x - 1}{x + 1} }, define fn+1(x)=f1(fn(x))f_{n + 1}(x) = f_1(f_n(x)) for n=1,2,3,…n = 1, 2, 3, …. It can be shown that f35=f5f_{35} = f_5. Determine AA, BB, CC, and DD so that f28(x)=Ax+BCx+D\displaystyle{ f_{28}(x) = \frac{Ax + B}{Cx + D} }.

Hints

Hint #1

Sure, you can compute f28f_{28} manually, but maybe there’s an easier and faster way?

Hint #2

Can you use f35=f5f_{35} = f_5 somehow to limit the amount of computation you need to do?

Hint #3

Work backwards from f35f_{35} using f35=f5f_{35} = f_5 until you can reach f28f_{28}.

Solution

Open to see the solution; try solving it first or see the hints above!

Per the problem statement, we know that:

fn+1(x)=f1(fn(x)) f_{n+1}(x) = f_1(f_n(x))

which tells us that fn(x)f_n(x) is equivalent to nn successive applications of f1f_1:

fn(x)=f1(f1(…f1(x)…))⏟f1 applied n times to x 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 fn(x)f_n(x) with fnf_n to eliminate the often-appearing (x)(x) term, which will make it easier to read. We will bring it back when necessary.

What we need to find is f28f_{28}, so we could just apply f1(x)f_1(x) recursively 2828 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 f35=f5f_{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:

⋮f36=f6f35=f5given in problem statementf34=f4⋮ \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 f35=f5f_{35} = f_5 implies that functions align forward and backward? Let’s look at the forward computation:

fn=fkf1(fn)=f1(fk)replace each side s with f1(s)fn+1=fk+1 \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:

fn=fkf1(fn−1)=f1(fk−1)from the definition abovefn−1=fk−1remove f1 application from each side (see note below) \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 f1f_1 application from each side above? Because f1f_1 is injective, which means that if f1(x)=f1(y)f_1(x) = f_1(y), then x=yx = y for all x,yx, y.

Why is f1f_1 injective? Let’s take f1(x)=2x−1x+1f_1(x) = \dfrac{2x - 1}{x + 1} and consider f1(a)f_1(a) and f1(b)f_1(b) and see if that implies that a=ba = b:

f1(a)=f1(b)2a−1a+1=2b−1b+1expand f1(2a−1)(b+1)=(2b−1)(a+1)cross-multiply2ab−b+2a−1=2ab−a+2b−1expand terms−b+2a=−a+2bsubtract 2ab−13a=3bcombine like termsa=bdivide by 3 \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 f1(a)=f1(b)  ⟹  a=bf_1(a) = f_1(b) \implies a = b for all a,ba, b.

Therefore, we can run f1f_1 applications backward from f35=f5f_{35} = f_5 to find other equivalences.

Since we need to find the definition of f28f_{28}, let’s run the equivalences backward enough to find what it’s equivalent to:

f35=f5given in problem statementf34=f4f33=f3f32=f2f31=f1f30=  ?f29=  ?f28=  ?what we’re trying to compute \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, fnf_n is only defined for n≥1n \ge 1, so we have to stop at f31=f1f_{31} = f_1, and then we can compute the rest of the functions iteratively.

First, note that since f31(x)=f1(f30(x))=f1(x)f_{31}(x) = f_1(f_{30}(x)) = f_1(x), we have f30(x)=xf_{30}(x) = x.

Second, we know that f30(x)=f1(f29(x))=xf_{30}(x) = f_1(f_{29}(x)) = x, so let’s compute f29f_{29}:

f30(x)=f1(f29(x))from problem statementf30=f1(f29)simplify notation per abovex=f1(f29)substitute f30 per abovex=2f29−1f29+1evaluate f1x(f29+1)=2f29−1x⋅f29+x=2f29−1distribute xx⋅f29−2f29=−x−1group like termsf29⋅(x−2)=−x−1factor out f29f29=−x−1x−2solve for f29f29=x+12−xsimplify signs \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 f28f_{28}:

f29=f1(f28)from problem statementx+12−x=f1(f28)substitute definition of f29x+12−x=2f28−1f28+1evaluate f1(x+1)(f28+1)=(2f28−1)(2−x)cross-multiplyx⋅f28+x+f28+1=4⋅f28−2x⋅f28−2+xexpand3x⋅f28−3f28=x−x−2−1=−3combine like termsx⋅f28−f28=−1divide by 3f28(x−1)=−1factor out f28f28=−1x−1solve for f28, solution Af28=11−xsimplify signs, solution B \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 AA, BB, CC, and DD to satisfy f28(x)=Ax+BCx+D 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.

f28(x)=Ax+BCx+Dfrom problem statement=11−xfrom solution B above=0x+1−x+1reorganize to match pattern \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, A=0;B=1;C=−1;D=1 \boxed{A = 0; \quad B = 1; \quad C = -1; \quad D = 1} \quad is one valid solution.

Another solution is:

f28(x)=Ax+BCx+Dfrom problem statement=−1x−1from solution A above=0x−1x−1reorganize to match pattern \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: A=0;B=−1;C=1;D=−1 \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-1. ■\quad \blacksquare