From Recursion to Inequality

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

From Recursion to Inequality

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: IDMC 2025 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

103 posts

#1 h Apr 20, 2025, 5:01 AM • 1 Y

Y by fe.

$\{a_n\}_{n\geq 1}$ is a sequence of real numbers with $a_1=1,\;a_2 =2$ such that for all $n\geq 1$
$a_{n+2}=\dfrac{a_{n+1}^{2}}{1+a_{n}}+a_{n+1}.$ Prove that

$\dfrac{1}{1+a_{1}+a_{2}}+\dfrac{1}{1+a_{2}+a_{3}}+\cdots + \dfrac{1}{1+a_{1403}+a_{1404}}>\dfrac{2^{1403}-1}{2^{1404}}.$
Proposed by Mojtaba Zare

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4918 posts

#2 h Apr 20, 2025, 9:09 AM • 1 Y

Y by Calc_1

First let show $a_{n+1} \geq 2a_{n}$
for $n=1$ it is true
$\frac{a_{n+1}}{a_n}=\frac{a_n}{1+a_{n-1}}+1 \geq \frac{2a_{n-1}}{1+a_{n-1}}+1 \geq 2$
$a_1=1,a_2=2,a_3=4,a_4=\frac{28}{3}>8=2^3$ and so $a_{n+1}>2^n$ for $n \geq 3$

$\frac{1}{1+a_n}=\frac{a_{n+2}-a_{n+1}}{a_{n+1}^2}$
$1+a_n+a_{n+1}=\frac{a_{n+1}^2}{a_{n+2}-a_{n+1}}+a_{n+1}=\frac{a_{n+1}a_{n+2}}{a_{n+2}-a_{n+1}}$
$\frac{1}{1+a_n+a_{n+1}}=\frac{1}{a_{n+1}}-\frac{1}{a_{n+2}}$

So $\dfrac{1}{1+a_{1}+a_{2}}+\dfrac{1}{1+a_{2}+a_{3}}+\cdots + \dfrac{1}{1+a_{1403}+a_{1404}}=\frac{1}{a_2}-\frac{1}{a_3}+\frac{1}{a_3}-\frac{1}{a_4}+...+\frac{1}{a_{1404}}-\frac{1}{a_{1405}}=\frac{1}{a_2}-\frac{1}{a_{1405}}>\frac{1}{2}-\frac{1}{2^{1404}}=\frac{2^{1403}-1}{2^{1404}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

missionjoshi.65

2 posts

missionjoshi.65

#3 h Apr 20, 2025, 10:34 AM • 1 Y

Y by khan.academy

I have a similar solution as above.
$a_{n+2} = a_{n+1} \left( \frac{a_{n+1}}{1+a_n} + 1 \right) = a_{n+1} \left( \frac{a_{n+1} + 1 + a_n}{1+a_n} \right)$
Dividing by $a_{n+1}$ , we get:

$\frac{a_{n+2}}{a_{n+1}} = \frac{1+a_n+a_{n+1}}{1+a_n}$
Rearranging this gives:

$1+a_n+a_{n+1} = (1+a_n)\frac{a_{n+2}}{a_{n+1}}$
$\frac{1}{1+a_n+a_{n+1}} = \frac{1}{(1+a_n)\frac{a_{n+2}}{a_{n+1}}} = \frac{a_{n+1}}{(1+a_n)a_{n+2}} = \frac{a_{n+2}-a_{n+1}}{a_{n+1}a_{n+2}} = \frac{1}{a_{n+1}} - \frac{1}{a_{n+2}}$
So the given inequality turns into
$\sum_{k=1}^{1403} \frac{1}{1+a_k+a_{k+1}} = \sum_{k=1}^{1403} \left( \frac{1}{a_{k+1}} - \frac{1}{a_{k+2}} \right) = \frac{1}{2} - \frac{1}{a_{1405}} > \frac{1}{2} - \frac{1}{2^{1404}}$
Hence it suffices to show that $a_{1405} > 2^{1404}$

Now we proceed by induction. Let $P(n)$ denote the induction statement.

$P(n): a_{n+1} > 2^{n}$ for $n \geq 3$ . It is easy to see that the base cases satisfy this for $n=3$ and $n=4$ .

Now, suppose it is true for $n = k$ , then we have

$a_{k+1} > 2^{k}$
Now, consider $P(k+1)$ :
$\begin{align*} a_{k+2} &= \frac{a^2_{k+1}}{1+a_{k}} + a_{k+1} \\ &> \frac{a_{k+1}^2}{a_{k+1}} + a_{k+1} \\ &> 2^{k+1} \end{align*}$
The second last inequality follows from $a_{k+1} - a_k > 1$ which is trivial from induction.

Thus, $a_{n+1} > 2^n \quad \forall \; n \geq 3$ which implies $a_{1405} > 2^{1404}$ and our proof is completed.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a