Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1990 USAMO Problems/Problem 2"

(wrote solution)
m
 
(4 intermediate revisions by 3 users not shown)
Line 7: Line 7:
 
(Recall that <math>\sqrt {\makebox[5mm]{}}</math> is understood to represent the positive [[square root]].) For each positive integer <math>n</math>, find all real solutions of the equation <math>\, f_n(x) = 2x \,</math>.
 
(Recall that <math>\sqrt {\makebox[5mm]{}}</math> is understood to represent the positive [[square root]].) For each positive integer <math>n</math>, find all real solutions of the equation <math>\, f_n(x) = 2x \,</math>.
  
−
== Solution ==
+
== Solution 1 ==
  
 
We define <math>f_0(x) = 8</math>.  Then the recursive relation holds for <math>n=0</math>, as well.
 
We define <math>f_0(x) = 8</math>.  Then the recursive relation holds for <math>n=0</math>, as well.
Line 29: Line 29:
 
The claim therefore holds by induction.  It then follows that for all nonnegative integers <math>n</math>, <math>x=4</math> is the unique solution to the equation <math>f_n(x) = 2x</math>.  <math>\blacksquare</math>
 
The claim therefore holds by induction.  It then follows that for all nonnegative integers <math>n</math>, <math>x=4</math> is the unique solution to the equation <math>f_n(x) = 2x</math>.  <math>\blacksquare</math>
  
 +
== Solution 2 ==
 +
We claim that the only solution is <math>\boxed{x=4}</math> for all such <math>n</math>. To show this, we consider all <math>x</math> and find solutions <math>n</math>.
  
−
{{alternate solutions}}
+
Before we consider solutions, we show that for all <math>x</math>, <math>f_n(x)</math> is positive for all positive integers <math>n</math> by induction. For our base case:
 +
<cmath>f_1(x)=\sqrt{x^2+48}\ge\sqrt{48}>0</cmath>
 +
so it is positive. Next, for our inductive step, assume for some <math>n=k-1</math> that <math>f_{k-1}(x)</math> is positive; thus <math>f_{k-1}(x)>0</math>, and we show that <math>f_k(x)</math> is positive:
 +
<cmath>f_k(x)=\sqrt{x^2+6f_{k-1}(x)}\ge\sqrt{0+6f_{k-1}(x)}>\sqrt{0+0}=0</cmath>
 +
thus <math>f_k(x)>0</math>, so we have proven the claim by induction.
  
−
==See also==
+
First, we consider negative <math>x</math>. We know that for negative <math>x</math>, if the equation were to have a solution, we would have <math>f_n(x)=2x<0</math> for some <math>n</math>. However, <math>f_n(x)</math> is always nonnegative since <math>f_n(x)</math> is always the square root of some number, which can never be negative; thus there are no solutions in this case.
 +
 
 +
Next, we consider <math>x=0</math>. Solutions would have to satisfy <math>f_n(0)=0</math>; we have previously shown that all <math>f_n(x)</math> are positive, so there are no such <math>n</math>.
 +
 
 +
Finally, we consider positive <math>x</math>. We divide this set into three groups: <math>x<4</math>, <math>x=4</math>, and <math>x>4</math>. We claim that for increasing <math>n</math>, <math>f_n(x)</math> is decreasing, constant, and increasing, respectively, and we prove this using induction. First, we analyze <math>x<4</math>. Then
 +
<cmath>f_1(x)<\sqrt{4^2+48}=\sqrt{64}=8</cmath>
 +
For our base case:
 +
<cmath>f_2(x)=\sqrt{x^2+6f_1(x)}<\sqrt{x^2+6\cdot8}=f_1(x)</cmath>
 +
Thus <math>f_2(x)<f_1(x)</math>. For our inductive step, if for some <math>n=k-1</math> we have <math>f_k(x)<f_{k-1}(x)</math>, we show that <math>f_{k+1}(x)<f_k(x)</math>:
 +
<cmath>f_{k+1}(x)=\sqrt{x^2+6f_k(x)}<\sqrt{x^2+6f_{k-1}(x)}=f_k(x)</cmath>
 +
Thus <math>f_1(x)>f_2(x)>f_3(x)>\ldots</math> and the conclusion follows.
 +
 
 +
Next, for <math>x=4</math>, <math>f_1(4)=8</math> by substituting. Then, if <math>f_{n-1}(4)=8</math>, we show that <math>f_n(4)=8</math> as well:
 +
<math>f_n(4)=\sqrt{x^2+6f_{n-1}(x)}=\sqrt{16+6\cdot8}=\sqrt{64}=8</math>
 +
so the sequence is constant. Notice that in this case, the equation we must solve becomes <math>f_n(4)=8</math>, which is true for all positive integers <math>n</math>.
 +
 
 +
Finally, we analyze <math>x>4</math>. Then
 +
<cmath>f_1(x)>\sqrt{4^2+48}=\sqrt{64}=8</cmath>
 +
For our base case:
 +
<cmath>f_2(x)=\sqrt{x^2+6f_1(x)}>\sqrt{x^2+6\cdot8}=f_1(x)</cmath>
 +
Thus <math>f_2(x)>f_1(x)</math>. For our inductive step, if for some <math>n=k-1</math> we have <math>f_k(x)>f_{k-1}(x)</math>, we show that <math>f_{k+1}(x)>f_k(x)</math>:
 +
<cmath>f_{k+1}(x)=\sqrt{x^2+6f_k(x)}>\sqrt{x^2+6f_{k-1}(x)}=f_k(x)</cmath>
 +
Thus <math>f_1(x)<f_2(x)<f_3(x)<\ldots</math> and the conclusion follows.
 +
 
 +
If for some positive integer <math>n</math> we have <math>f_n(x)=2x</math>, then:
 +
 
 +
\begin{align*}
 +
f_n(x)&=\sqrt{x^2+6f_{n-1}(x)}\\
 +
2x&=\sqrt{x^2+6f_{n-1}(x)}\\
 +
4x^2&=x^2+6f_{n-1}(x)\\
 +
3x^2&=6f_{n-1}(x)\\
 +
\frac{1}{2}x^2&=f_{n-1}(x)
 +
\end{align*}
 +
However, if <math>0<x<4</math> is a solution, then we must have <math>f_{n-1}(x)>f_n(x)</math>; substituting values yields <math>\frac{1}{2}x^2>2x</math>, which implies <math>x>4</math>; this is a contradiction. Similarly, if <math>x>4</math> is a solution, then we must have <math>f_{n-1}(x)<f_n(x)</math>; substituting values yields <math>\frac{1}{2}x^2<2x</math>, which implies <math>x<4</math>; this is also a contradiction.
 +
 
 +
As a result, since we have already established that <math>x=4</math> is a solution for all <math>n</math> and no other <math>x</math> can be solutions, we conclude that for each positive integer <math>n</math>, the only real solution of the equation is <math>x=4</math>.
 +
 
 +
~ [https://artofproblemsolving.com/wiki/index.php/User:Eevee9406 eevee9406]
 +
 
 +
==See Also==
  
 
{{USAMO box|year=1990|num-b=1|num-a=3}}
 
{{USAMO box|year=1990|num-b=1|num-a=3}}
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356624#p356624 Discussion on AoPS/MathLinks]
 
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356624#p356624 Discussion on AoPS/MathLinks]
 +
{{MAA Notice}}
  
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Latest revision as of 15:48, 16 March 2025

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{align*} f_n(x)&=\sqrt{x^2+6f_{n-1}(x)}\\ 2x&=\sqrt{x^2+6f_{n-1}(x)}\\ 4x^2&=x^2+6f_{n-1}(x)\\ 3x^2&=6f_{n-1}(x)\\ \frac{1}{2}x^2&=f_{n-1}(x) \end{align*} 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

See Also

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

These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions. AMC Logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_2&oldid=245151"