Art of Problem Solving
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

2001 IMO Shortlist Problems/A3: Difference between revisions

← Older edit
mNo edit summary
Maphycom (talk | contribs)
editor
76 edits
No edit summary
 
(6 intermediate revisions by one other user not shown)
Line 4: Line 4:
<cmath> \frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2 + x_2^2} + \dotsb + \frac{x_n}{1+ x_1^2  + \dotsb + x_n^2} < \sqrt{n} . </cmath>
<cmath> \frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2 + x_2^2} + \dotsb + \frac{x_n}{1+ x_1^2  + \dotsb + x_n^2} < \sqrt{n} . </cmath>


== Solution ==
== Solution 1 ==


We prove the following general inequality, for arbitrary positive real <math>k</math>:
We prove the following general inequality, for arbitrary positive real <math>k</math>:
Line 25: Line 25:
<cmath> (\lvert \sin t \rvert + \sqrt{n} \cos t)/k \le (1 + n)^{1/2}(\sin^2 t + \cos^2 t)^{1/2}/k = \sqrt{n+1}/k, </cmath>
<cmath> (\lvert \sin t \rvert + \sqrt{n} \cos t)/k \le (1 + n)^{1/2}(\sin^2 t + \cos^2 t)^{1/2}/k = \sqrt{n+1}/k, </cmath>
with equality only when <math>(\lvert \sin t \rvert, \cos t) = (1/\sqrt{n^2+1}, n/\sqrt{n^2+1}</math>.  Since <math>\left\lvert n/\sqrt{n^2+1} \right\rvert < 1</math>, our equality cases never coincide, so we have the desired strict inequality for <math>n+1</math>.  Thus our inequality is true by induction.  The problem statement therefore follows from setting <math>k=1</math>.  <math>\blacksquare</math>
with equality only when <math>(\lvert \sin t \rvert, \cos t) = (1/\sqrt{n^2+1}, n/\sqrt{n^2+1}</math>.  Since <math>\left\lvert n/\sqrt{n^2+1} \right\rvert < 1</math>, our equality cases never coincide, so we have the desired strict inequality for <math>n+1</math>.  Thus our inequality is true by induction.  The problem statement therefore follows from setting <math>k=1</math>.  <math>\blacksquare</math>
== Solution 2 ==
By the [[Cauchy-Schwarz Inequality]]
<math>a_1+a_2+.....+a_k \leq \sqrt{n}.\sqrt{a_1^2+a_2^2+................+a_k^2}</math>
For all real numbers. <math>a_1,a_2,....</math> 
Hence it is only required to prove <math>a_1^2+a_2^2+................+a_k^2<1</math> where <math>a_k=\dfrac{x_k}{1+x_1^2+... x_k^2}</math>
for <math>k \geq 2</math>, <math>a_k^2=(\dfrac{x_k}{1+x_1^2+... x_k^2})^2 < \dfrac{x_k^2}{(1+x_1^2+... x_{k-1}^2)(1+x_1^2+... x_k^2)} = \dfrac{1}{1+x_1^2+... x_{k-1}^2}-\dfrac{1}{1+x_1^2+... x_k^2}</math>
For k=1, <math>a_1^2 = 1-\dfrac{1}{1+x_1^2}</math>
Summing these inequalities, the right-hand side yields
<math>\sum_{n=1}^{k}a_n^2\leq 1</math>
Hence Proved by Maths1234RC
P.S. This is my first solution on AOPS.<math>\blacksquare</math>
== Solution 3 ==
Let <math>S_n = 1 + x^2 + \cdots + x_n^2</math> where <math>S_0 = 1</math> by convention.
Rewriting the inequality,
<cmath>
\frac{x_1}{S_1} + \frac{x_2}{S_2} + \cdots + \frac{x_n}{S_n} < \sqrt{n}
</cmath>
must be proven.
Note that by Chebyshev's inequality, the following could be driven.
<cmath>
\left( \sum_{i = 1}^n \frac{x_i}{S_i} \right)^2 \leq n \left( \sum_{i = 1}^n \frac{x_i^2}{S_i^2} \right)
</cmath>
Therefore, it suffices to prove that <math>\sum_{i = 1}^n \frac{x_i^2}{S_i^2} < 1</math>. Notice that <math>x_i^2 = S_i - S_{i - 1}</math>.
  <math>Lemma.</math>
  <cmath>
  \sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i^2} < 1
  </cmath>
  is true.
<math>Proof.</math>
Because <math>S_n</math> is a monotonically increasing sequence, <math>S_i^2 \geq S_i \cdot S_{i - 1}</math>.
<cmath>
\sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i^2}
\leq \sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i \cdot S_{i - 1}}
= \sum_{i = 1}^n \left( \frac{1}{S_{i - 1}} - \frac{1}{S_i} \right)
= \frac{1}{S_0} - \frac{1}{S_n}
= 1 - \frac{1}{S_n} < 1
</cmath>
<math>\blacksquare</math>
Hence, the inequality is true.
~MaPhyCom (Thinking Tree)
I also have a video explanation of this solution!!
[https://youtu.be/mjUccETe65w  Please consider subscribing :))]




Latest revision as of 03:12, 25 September 2025

Problem

Let $x_1, x_2, \dotsc, x_n$ be arbitrary real numbers. Prove the inequality \[\frac{x_1}{1+x_1^2} + \frac{x_2}{1+x_1^2 + x_2^2} + \dotsb + \frac{x_n}{1+ x_1^2 + \dotsb + x_n^2} < \sqrt{n} .\]

Solution 1

We prove the following general inequality, for arbitrary positive real $k$: \[\sum_{j=1}^n \frac{x_j}{k^2 + \sum_{i=1}^j x_i^2} \le \sqrt{n}/k ,\] with equality only when $n=0$.

We proceed by induction on $n$. For $n=0$, we have trivial equality. Now, suppose our inequality holds for $n$. Then by inductive hypothesis, \[\sum_{j=1}^{n+1} \frac{x_j}{k^2 + \sum_{i=1}^j x_i^2} = \frac{x_1}{k^2 + x_1^2} + \sum_{j=2}^{n+1} \frac{x_j}{k^2 + x_1^2 + \sum_{i=2}^j x_i^2} \le \frac{x_1}{k^2 + x_1^2} + \frac{\sqrt{n}}{\sqrt{k^2 + x_1^2}} .\] If we let $t= \text{Arcsin} \left(x_1/\sqrt{x_1^2 +k^2} \right)$, then we have \[\frac{x_1}{k^2 + x_1^2} + \frac{\sqrt{n}}{\sqrt{k^2+x_1^2}} = (\sin t \cos t + \sqrt{n} \cos t)/k \le (\lvert \sin t \rvert + \sqrt{n} \cos t)/k ,\] with equality only if $\cos t= \pm 1$. By the Cauchy-Schwarz Inequality, \[(\lvert \sin t \rvert + \sqrt{n} \cos t)/k \le (1 + n)^{1/2}(\sin^2 t + \cos^2 t)^{1/2}/k = \sqrt{n+1}/k,\] with equality only when $(\lvert \sin t \rvert, \cos t) = (1/\sqrt{n^2+1}, n/\sqrt{n^2+1}$. Since $\left\lvert n/\sqrt{n^2+1} \right\rvert < 1$, our equality cases never coincide, so we have the desired strict inequality for $n+1$. Thus our inequality is true by induction. The problem statement therefore follows from setting $k=1$. $\blacksquare$

Solution 2

By the Cauchy-Schwarz Inequality $a_1+a_2+.....+a_k \leq \sqrt{n}.\sqrt{a_1^2+a_2^2+................+a_k^2}$ For all real numbers. $a_1,a_2,....$ Hence it is only required to prove $a_1^2+a_2^2+................+a_k^2<1$ where $a_k=\dfrac{x_k}{1+x_1^2+... x_k^2}$

for $k \geq 2$, $a_k^2=(\dfrac{x_k}{1+x_1^2+... x_k^2})^2 < \dfrac{x_k^2}{(1+x_1^2+... x_{k-1}^2)(1+x_1^2+... x_k^2)} = \dfrac{1}{1+x_1^2+... x_{k-1}^2}-\dfrac{1}{1+x_1^2+... x_k^2}$

For k=1, $a_1^2 = 1-\dfrac{1}{1+x_1^2}$

Summing these inequalities, the right-hand side yields $\sum_{n=1}^{k}a_n^2\leq 1$

Hence Proved by Maths1234RC P.S. This is my first solution on AOPS.$\blacksquare$

Solution 3

Let $S_n = 1 + x^2 + \cdots + x_n^2$ where $S_0 = 1$ by convention.

Rewriting the inequality, \[\frac{x_1}{S_1} + \frac{x_2}{S_2} + \cdots + \frac{x_n}{S_n} < \sqrt{n}\] must be proven.

Note that by Chebyshev's inequality, the following could be driven. \[\left( \sum_{i = 1}^n \frac{x_i}{S_i} \right)^2 \leq n \left( \sum_{i = 1}^n \frac{x_i^2}{S_i^2} \right)\] Therefore, it suffices to prove that $\sum_{i = 1}^n \frac{x_i^2}{S_i^2} < 1$. Notice that $x_i^2 = S_i - S_{i - 1}$. 

 $Lemma.$
 \[\sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i^2} < 1\]
 is true.

$Proof.$ Because $S_n$ is a monotonically increasing sequence, $S_i^2 \geq S_i \cdot S_{i - 1}$. \[\sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i^2} \leq \sum_{i = 1}^n \frac{S_i - S_{i - 1}}{S_i \cdot S_{i - 1}} = \sum_{i = 1}^n \left( \frac{1}{S_{i - 1}} - \frac{1}{S_i} \right) = \frac{1}{S_0} - \frac{1}{S_n} = 1 - \frac{1}{S_n} < 1\] $\blacksquare$

Hence, the inequality is true.

~MaPhyCom (Thinking Tree)

I also have a video explanation of this solution!! Please consider subscribing :))


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

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2001_IMO_Shortlist_Problems/A3&oldid=261478"