## Saturday, December 31, 2005

### Over and Over Again. Topic: Algebra. Level: Olympiad.

Problem: (1990 USAMO - #2) A sequence of functions $\{f_n(x) \}$, is defined recursively as follows:

$f_1(x) = \sqrt{x^2 + 48}, \quad \mbox{and} \\ f_{n+1}(x) = \sqrt{x^2 + 6f_n(x)} \quad \mbox{for } n \geq 1$

For each positive integer n, find all real solutions of the equation $f_n(x) = 2x$.

Solution: So $n$ can go to infinity, which means it's probably not going to be easy to go through each $n$ one by one.

Let's start with $n=1$: $\sqrt{x^2+48} = 2x \Rightarrow 3x^2 = 48 \Rightarrow x = 4$ (we ignore the negative solution because clearly a square root cannot be negative).

Moving on to $n=2$, we find $x=4$ again as the only solution.

Here we guess that $x = 4$ is a solution for all $n$. This can easily be shown by a quick induction with base case $n=1,2$.

If $x = 4$ is a solution for $n = k$, then $f_k(4) = 8 \Rightarrow f_{k+1}(4) = \sqrt{4^2+6f_k(4)} = \sqrt{4^2+6\cdot8} = 8$ so $4$ is a solution for $n = k+1$ as well. So $x = 4$ is always a solution.

Now we're like $x = 4$ is probably the only solution because it'd be too hard to find any other ones if they were out there. So we split into two cases ($x$ always positive because square roots are positive):

CASE 1: $x < 4$.

Then $f_1(x) = \sqrt{x^2+48} > 2x$. Inducting again, we have

$f_k(x) > 2x \Rightarrow f_{k+1}(x) = \sqrt{x^2+6f_k(x)} > \sqrt{x^2+12x} > 2x$ (last step using $x<4$). So there are no solutions.

CASE 2: $x > 4$.

Then $f_1(x) = \sqrt{x^2+48} < 2x$. Inducting, we have

$f_k(x) < 2x \Rightarrow f_{k+1}(x) = \sqrt{x^2+6f_k(x)} < \sqrt{x^2+12x} < 2x$ (last step using $x>4$). So there are no solutions here either.

Therefore, the only solution for all $n$ is $x = 4$. QED.

--------------------

Comment: Don't think this was as easy as the previous problem, but still not difficult for USAMO, at least nowadays.