The function $f(x)=x^2+ \sin x$ and the sequence of positive numbers $\{ a_n \}$ satisfy $a_1=1$, $f(a_n)=a_{n-1}$, where $n \geq 2$. Prove that there exists a positive integer $n$ such that $a_1+a_2+ \dots + a_n > 2020$.
Miku3D wrote:
The function $f(x)=x^2+ \sin x$ and the sequence of positive numbers $\{ a_n \}$ satisfy $a_1=1$, $f(a_n)=a_{n-1}$, where $n \geq 2$. Prove that there exists a positive integer $n$ such that $a_1+a_2+ \dots + a_n > 2020$.
Let $u=1+\frac{\sqrt 2}2$
If is easy to show that $a_n\ge u$ $\implies$ $u_{n+1}=u_n^2+\sin u_n\ge u_n^2-1\ge u_n+u$
And since $a_2=1+\sin 1>1+\sin\frac{\pi}4=u$, we get $a_{n+1}\ge a_n+u$ $\forall n\ge 1$
Hence the claim.
@above I think you misread the condition as $f(a_{n-1})=a_n$ instead of $f(a_n)=a_{n-1}$ by accident. I found it weird but that's really what the problem statement was
Anyways, here's my solution at the contest
We first prove the following 2 Lemmas
Lemma 1: $\sin x \leq x \text{ } \forall x \geq 0$
Proof of Lemma 1Let $f(x)=x-\sin x$
$$\therefore f'(x)=1-\cos x \geq 1-1 =0 \text{ } \forall x \in \mathbb{R}$$Where $f'(x)$ refers to the derivative of $f(x)$
Thus, $f$ is a nondecreasing function
$$\therefore f(x) \geq f(0) = 0 \text{ } \forall x \geq 0$$$$\implies x - \sin x \geq 0 \text{ } \forall x \geq 0$$$$\implies x \geq sinx \text{ } \forall x \geq 0$$
Thus, the Lemma is proven $\blacksquare$
Lemma 2: The sum $\sum_{i=1}^{n} \frac{1}{i}$ is divergent as $n$ approaches infinity, or in other words, $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots$ is unbounded.
Proof of Lemma 2Note that we can split the set of positive integers into
$$A_0 = \{1\}$$$$A_1 = \{2\}$$$$A_2 = \{3,4\}$$$$A_3 = \{5,6,7,8\}$$$$\cdots$$$$A_i = \{ x|x \in \mathbb{N}, 2^{i-1}<x \leq 2^{i} \}$$$$\cdots$$
Clearly, $A_i$ has $2^{i}-2^{i-1}=2^{i-1}$ elements $\forall i \in \mathbb{N}$
$$\therefore \sum_{i=1}^{\infty} \frac{1}{i}
=\sum_{i=1}^{\infty} \left ( \sum_{x \in A_i} \frac{1}{x} \right ) + \frac{1}{1}$$$$\geq \sum_{i=1}^{\infty} \left ( \sum_{x \in A_i} \frac{1}{2^i} \right ) + 1$$$$=\sum_{i=1}^{\infty} \left ( \frac{2^{i-1}}{2^i} \right ) +1$$$$=\sum_{i=1}^{\infty} \left ( \frac{1}{2} \right ) +1$$$$=\infty \cdot \frac{1}{2} +1$$Which is clearly unbounded
$\therefore \sum_{i=1}^{\infty} \frac{1}{i}$ is also unbounded
Thus, the Lemma is proven $\blacksquare$
Define a sequence of positive reals $\{b_n\}$ such that $b_1=1$ and
$$b_{n+1}^{2}+b_{n+1}=b_{n} \forall n \in \mathbb{N}$$
Let $g(x)=x^2+x$. Note that it is a strictly monotonic increasing function in the interval $[0,\infty )$ and $g(0)=0$, so $\forall t \in \mathbb{R}^{+}$, $\exists$ a unique $x \in \mathbb{R}^{+}$ such that $g(x)=t$.
$\therefore$ given a positive real $b_n$, $\exists$ a unique $b_{n+1} \in \mathbb{R}^{+}$ that satisfies the above recurrence.
Since the sequence $\{b_n\}$ starts with 1, then it is well defined.
Claim 1: $a_n \geq b_n \forall n \in \mathbb{R}^{+}$
Proof by InductionClearly, $a_1=b_1=1 \implies a_1 \geq b_1$, so it is true for $n=1$
Suppose it is true for $n=k \in \mathbb{N}$, so $a_k \geq b_k$
Thus,
$$a_{k+1}^{2} + a_{k+1} \stackrel{ \text{Lemma 1} }{\geq} a_{k+1}^2+ \sin a_{k+1} = a_k \geq b_k = b_{k+1}^2 +b_{k+1}$$Again, note that $g(x)=x^2+x$ is strictly monotonic increasing in the interval $[0,\infty )$, and we know that $a_{k+1}$ and $b_{k+1}$ both lie in that interval. Thus, the above inequality implies that $a_{k+1} \geq b_{k+1}$.
$\therefore$ it is true for $n=k+1$ as well.
$\therefore$ it is true $\forall n \in \mathbb{N}$ by induction.
Thus, the Claim is proven $\blacksquare$
Claim 2: $b_n \geq \frac{1}{n} \forall n \in \mathbb{N}$
Proof by InductionClearly, $b_1=1 \implies b_1 \geq \frac{1}{1}$, so it is true for $n=1$
Suppose that it is true for $n=k \in \mathbb{N}$, so $b_k \geq \frac{1}{k}$
Note that
$$k^2+2k < k^2+2k+1$$$$\implies k(k+2)<(k+1)^2$$$$\implies \frac{1}{k+1} \cdot \frac{k+2}{k+1} < \frac{1}{k}$$$$\implies \frac{1}{k+1} \left ( \frac{1}{k+1}+1 \right ) < \frac{1}{k}$$$$\implies \left ( \frac{1}{k+1} \right ) ^2 +\frac{1}{k}< \frac{1}{k}$$Thus,
$$b_{k+1}^{2} + b_{k+1} = b_k \geq \frac{1}{k} \geq \left ( \frac{1}{k+1} \right ) ^2 +\frac{1}{k}$$
Again, since $g(x)=x^2+x$ is monotonic increasing in $[0,\infty)$ and $b_k+1$ and $\frac{1}{k+1}$ both lie in that interval, the above inequality implies that $b_{k+1} \geq \frac{1}{k+1}$
$\therefore$ it is true for $n=k+1$ as well
$\therefore$ it is true $\forall n \in \mathbb{N}$ by induction
Thus, the Claim is proven $\blacksquare$
Therefore,
$$\sum_{i=1}^{n}a_i \stackrel{\text{Claim 1}}{\geq}
\sum_{i=1}^{n}b_i \stackrel{\text{Claim 2}}{\geq}
\sum_{i=1}^{n} \frac{1}{i} \text{ } \forall n \in \mathbb{N}$$Since the sum $\sum_{i=1}^{n} \frac{1}{i}$ is divergent by Lemma 2, then $\exists$ a sufficiently large $n \in \mathbb{N}$ such that $\sum_{i=1}^{n} \frac{1}{i} > 2020$.
$\therefore$ picking that sufficiently large $n \in \mathbb{N}$ gives
$$\sum_{i=1}^{n}a_i \geq \sum_{i=1}^{n} \frac{1}{i} > 2020$$as desired
$\therefore \exists n \in \mathbb{N}$ such that $a_1 + a_2 + \cdots + a_n > 2020 \blacksquare$