1990 USAMO Problems/Problem 2

Problem

A sequence of functions $\, \{f_n(x) \} \,$ is defined recursively as follows: $\begin{align*} f_1(x) &= \sqrt {x^2 + 48}, \quad \text{and} \\ f_{n + 1}(x) &= \sqrt {x^2 + 6f_n(x)} \quad \text{for } n \geq 1. \end{align*}$ (Recall that $\sqrt {\makebox[5mm]{}}$ is understood to represent the positive square root.) For each positive integer $n$ , find all real solutions of the equation $\, f_n(x) = 2x \,$ .

Solution 1

We define $f_0(x) = 8$ . Then the recursive relation holds for $n=0$ , as well.

Since $f_n (x) \ge 0$ for all nonnegative integers $n$ , it suffices to consider nonnegative values of $x$ .

We claim that the following set of relations hold true for all natural numbers $n$ and nonnegative reals $x$ : $\begin{align*} f_n(x) &< 2x \text{ if }x>4 ; \\ f_n(x) &= 2x \text{ if }x=4 ; \\ f_n(x) &> 2x \text{ if }x<4 . \end{align*}$ To prove this claim, we induct on $n$ . The statement evidently holds for our base case, $n=0$ .

Now, suppose the claim holds for $n$ . Then $\begin{align*} f_{n+1}(x) &= \sqrt{x^2 + 6f_n(x)} < \sqrt{x^2+12x} < \sqrt{4x^2} = 2x, \text{ if } x>4 ; \\ f_{n+1}(x) &= \sqrt{x^2 + 6f_n(x)} = \sqrt{x^2 + 12x} = \sqrt{4x^2} = 2x, \text{ if } x=4 ; \\ f_{n+1}(x) &= \sqrt{x^2 + 6f_n(x)} > \sqrt{x^2+12x} > \sqrt{4x^2} = 2x, \text{ if } x<4 . \end{align*}$ The claim therefore holds by induction. It then follows that for all nonnegative integers $n$ , $x=4$ is the unique solution to the equation $f_n(x) = 2x$ . $\blacksquare$

Solution 2

We claim that the only solution is $\boxed{x=4}$ for all such $n$ . To show this, we consider all $x$ and find solutions $n$ .

Before we consider solutions, we show that for all $x$ , $f_n(x)$ is positive for all positive integers $n$ by induction. For our base case: $f_1(x)=\sqrt{x^2+48}\ge\sqrt{48}>0$ so it is positive. Next, for our inductive step, assume for some $n=k-1$ that $f_{k-1}(x)$ is positive; thus $f_{k-1}(x)>0$ , and we show that $f_k(x)$ is positive: $f_k(x)=\sqrt{x^2+6f_{k-1}(x)}\ge\sqrt{0+6f_{k-1}(x)}>\sqrt{0+0}=0$ thus $f_k(x)>0$ , so we have proven the claim by induction.

First, we consider negative $x$ . We know that for negative $x$ , if the equation were to have a solution, we would have $f_n(x)=2x<0$ for some $n$ . However, $f_n(x)$ is always nonnegative since $f_n(x)$ is always the square root of some number, which can never be negative; thus there are no solutions in this case.

Next, we consider $x=0$ . Solutions would have to satisfy $f_n(0)=0$ ; we have previously shown that all $f_n(x)$ are positive, so there are no such $n$ .

Finally, we consider positive $x$ . We divide this set into three groups: $x<4$ , $x=4$ , and $x>4$ . We claim that for increasing $n$ , $f_n(x)$ is decreasing, constant, and increasing, respectively, and we prove this using induction. First, we analyze $x<4$ . Then $f_1(x)<\sqrt{4^2+48}=\sqrt{64}=8$ For our base case: $f_2(x)=\sqrt{x^2+6f_1(x)}<\sqrt{x^2+6\cdot8}=f_1(x)$ Thus $f_2(x)<f_1(x)$ . For our inductive step, if for some $n=k-1$ we have $f_k(x)<f_{k-1}(x)$ , we show that $f_{k+1}(x)<f_k(x)$ : $f_{k+1}(x)=\sqrt{x^2+6f_k(x)}<\sqrt{x^2+6f_{k-1}(x)}=f_k(x)$ Thus $f_1(x)>f_2(x)>f_3(x)>\ldots$ and the conclusion follows.

Next, for $x=4$ , $f_1(4)=8$ by substituting. Then, if $f_{n-1}(4)=8$ , we show that $f_n(4)=8$ as well: $f_n(4)=\sqrt{x^2+6f_{n-1}(x)}=\sqrt{16+6\cdot8}=\sqrt{64}=8$ so the sequence is constant. Notice that in this case, the equation we must solve becomes $f_n(4)=8$ , which is true for all positive integers $n$ .

Finally, we analyze $x>4$ . Then $f_1(x)>\sqrt{4^2+48}=\sqrt{64}=8$ For our base case: $f_2(x)=\sqrt{x^2+6f_1(x)}>\sqrt{x^2+6\cdot8}=f_1(x)$ Thus $f_2(x)>f_1(x)$ . For our inductive step, if for some $n=k-1$ we have $f_k(x)>f_{k-1}(x)$ , we show that $f_{k+1}(x)>f_k(x)$ : $f_{k+1}(x)=\sqrt{x^2+6f_k(x)}>\sqrt{x^2+6f_{k-1}(x)}=f_k(x)$ Thus $f_1(x)<f_2(x)<f_3(x)<\ldots$ and the conclusion follows.

If for some positive integer $n$ we have $f_n(x)=2x$ , then:

$\begin{aligned} f_{n} (x) & = \sqrt{x^{2} + 6 f_{n - 1} (x)} \\ 2 x & = \sqrt{x^{2} + 6 f_{n - 1} (x)} \\ 4 x^{2} & = x^{2} + 6 f_{n - 1} (x) \\ 3 x^{2} & = 6 f_{n - 1} (x) \\ \frac{1}{2} x^{2} & = f_{n - 1} (x) \end{aligned}$ However, if $0<x<4$ is a solution, then we must have $f_{n-1}(x)>f_n(x)$ ; substituting values yields $\frac{1}{2}x^2>2x$ , which implies $x>4$ ; this is a contradiction. Similarly, if $x>4$ is a solution, then we must have $f_{n-1}(x)<f_n(x)$ ; substituting values yields $\frac{1}{2}x^2<2x$ , which implies $x<4$ ; this is also a contradiction.

As a result, since we have already established that $x=4$ is a solution for all $n$ and no other $x$ can be solutions, we conclude that for each positive integer $n$ , the only real solution of the equation is $x=4$ .

~ eevee9406

1990 USAMO (Problems • Resources)
Preceded by Problem 1	Followed by Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

Page

Toolbox

Search

1990 USAMO Problems/Problem 2

Contents

Problem

Solution 1

Solution 2

See Also