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"

(→‎Solution: solution template)
(wrote solution)
Line 1: Line 1:
−
==Problem==
+
== Problem ==
 
A sequence of [[function]]s <math>\, \{f_n(x) \} \,</math> is defined [[recursion|recursively]] as follows:
 
A sequence of [[function]]s <math>\, \{f_n(x) \} \,</math> is defined [[recursion|recursively]] as follows:
−
 
+
<cmath> \begin{align*}
−
<math>
+
f_1(x) &= \sqrt {x^2 + 48}, \quad \text{and} \\
−
f_1(x) = \sqrt {x^2 + 48}, \quad \mbox{and} \\
+
f_{n + 1}(x) &= \sqrt {x^2 + 6f_n(x)} \quad \text{for } n \geq 1.
−
f_{n + 1}(x) = \sqrt {x^2 + 6f_n(x)} \quad \mbox{for } n \geq 1.
+
\end{align*} </cmath>
−
</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>.
 
(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 ==
−
<math>x</math> must be nonnegative, since the natural root of any number is <math>\ge 0</math>. Solving for <math>n=1</math>, we get <math>x=4</math> and only <math>4</math>. We solve for <math>n=2</math>:
 
  
−
<math>2x=\sqrt{x^2+6\sqrt{x^2+48}}</math>
+
We define <math>f_0(x) = 8</math>.  Then the recursive relation holds for <math>n=0</math>, as well.
  
−
<math>3x^2=6\sqrt{x^2+48}</math>
+
Since <math>f_n (x) \ge 0</math> for all nonnegative integers <math>n</math>, it suffices to consider nonnegative values of <math>x</math>.
  
−
<math>x^4=4x^2+192</math>
+
We claim that the following set of relations hold true for all natural numbers <math>n</math> and nonnegative reals <math>x</math>:
 +
<cmath> \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*} </cmath>
 +
To prove this claim, we induct on <math>n</math>.  The statement evidently holds for our base case, <math>n=0</math>.
  
−
<math>x^2=\dfrac{4+28}{2}=16</math>
+
Now, suppose the claim holds for <math>n</math>.  Then
 +
<cmath> \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*} </cmath>
 +
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>
  
−
<math>x=4</math>
 
  
−
We get <math>x=4</math> again. We can conjecture that <math>x=4</math> is the only solution.
+
{{alternate solutions}}
  
−
Plugging <math>2x=8</math> into <math>f_n(x)</math>, we get
+
==See also==
  
−
<cmath>f_{n+1}(x)=\sqrt{x^2+48}</cmath>
+
{{USAMO box|year=1990|num-b=1|num-a=3}}
 +
* [http://www.artofproblemsolving.com/Forum/viewtopic.php?p=356624#p356624 Discussion on AoPS/MathLinks]
  
−
So if 4 is a solution for <math>n=x</math>, it is a solution for <math>n=x+1</math>. From [[induction]], <math>4</math> is a solution for all <math>n</math>.
 
−
 
−
==See also==
 
−
{{USAMO box|year=1990|num-b=1|num-a=3}}
 
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]

Revision as of 18:59, 11 January 2008

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

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$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

See also

1990 USAMO (Problems • Resources)
Preceded by
Problem 1 		Followed by
Problem 3
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1990_USAMO_Problems/Problem_2&oldid=22329"