Reciprocal Sums and Random Bounds

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

Reciprocal Sums and Random Bounds

G H J

Reveal topic tags

recurrence relation

L

G H BBookmark kLocked kLocked NReply

Source: Indian Statistical Institute Entrance UGB 2023/6

The post below has been deleted. Click to close.

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

458 posts

#1 h May 14, 2023, 1:04 PM • 1 Y

Y by GeoKing

Let $\{u_n\}_{n \ge 1}$ be a sequence of real numbers defined as $u_1 = 1$ and
$u_{n+1} = u_n + \frac{1}{u_n} \text{ for all $n \ge 1$.}$ Prove that $u_n \le \frac{3\sqrt{n}}{2}$ for all $n$ .

This post has been edited 4 times. Last edited by SatisfiedMagma, Apr 10, 2025, 4:01 PM

Z K Y

The post below has been deleted. Click to close.

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

10 posts

#2 h May 14, 2023, 1:21 PM • 3 Y

Y by GeoKing, Ghoshadi, maths_arka

for $n \ge 2$ we get $u_n \ge 2$
induction base case n=1,2: obviously true
inductive step for $n \ge 2$ : $u_{n+1}^2 = u_n^2+\frac{1}{u_n^2} +2 \le u_n^2 + \frac{1}{4} +2 \le \frac{9n}{4} + \frac{1}{4} +2 = \frac{9(n+1)}{4}$
so, $u_{n+1} \le \frac{3\sqrt{(n+1)}}{2}$

Z K Y

The post below has been deleted. Click to close.

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

1082 posts

#3 h May 14, 2023, 1:25 PM • 1 Y

Y by GeoKing

Let $n \geqslant 2$ . Easy to see that $u_n \geqslant 1, \forall n \in \mathcal{N}$ and that $x+1/x > y+1/y$ if $x>y \geqslant 1$ . So, wi will use induction
Induction step: $u_{n+1}=u_n+\frac{1}{u_n} \leqslant \frac{3\sqrt{n}}{2} + \frac{1}{\frac{3\sqrt{n}}{2}} \leqslant \frac{3\sqrt{n+1}}{2}$ which is obvious.

Z K Y

The post below has been deleted. Click to close.

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

Project_Donkey_into_M4

147 posts

Project_Donkey_into_M4

#4 h May 14, 2023, 6:23 PM

Y by

$\frac{3\sqrt{n}}{2}\geq u_n=\frac{u_{n+1}\pm \sqrt{u_{n+1}^2-4}}{2} \implies u_{n+1} \leq \frac{9n+4}{6\sqrt n} \leq \frac{3\sqrt{n+1}}{2}$

Z K Y

The post below has been deleted. Click to close.

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

11236 posts

#5 h May 16, 2023, 12:23 AM

Y by

Let $v_n=u_n^2$ . Clearly $v_n>0$ , so by induction $v_n$ is increasing. Now we easily find that $v_{n+1}=v_n+\frac1{v_n}+2$ , so $v_2=4$ and $v_n\ge4$ for all $n\ge2$ . Now, for induction suppose that $v_n\le\frac{9n}4$ for some $n\ge2$ . Note that $x+\frac1x$ is increasing for $x\ge4$ , so $v_n+\frac1{v_n}\le\frac{9n}4+\frac4{9n}$ . Then, since:
$\begin{align*} \frac{9(n+1)}4-v_{n+1}&=\frac{9(n+1)}4-v_n-\frac1{v_n}-2\\ &\ge\frac{9(n+1)}4-\frac{9n}4-\frac4{9n}-2\\ &=\frac{x-\frac{16}9}{4x}\\ &\ge0 \end{align*}$ since $x\ge4$ . Then, since $u_n>0$ and $v_1=1\le\frac94$ and $v_2=4\le\frac92$ we're done by induction.

Z K Y

The post below has been deleted. Click to close.

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

458 posts

#6 h May 20, 2023, 12:04 PM

Y by

Messy quadratics and induction. Here's just a different way to write the solution but the idea is the same. Got slightly hinted from primesarespecial because I never trust myself.

Solution: We will prove this by induction. The base case of $n = 2$ is easy to check. For the hypothesis, assume that $u_k \le \frac{3\sqrt{k}}{2}$ . We wish to show that $u_{k+1}\le \frac{3\sqrt{k+1}}{2}$ . Put $n = k$ in the recurrence and solve the quadratic for $u_k$ in terms of $u_{k+1}$ . One would get
$u_k = \frac{u_{k+1} + \sqrt{u_{k+1}^2-4}}{2}$ where we will ignore the negative sign of square root since the sequence is strictly increasing. Here's the final part, assume for the sake of contradiction that $u_{k+1} > \frac{3\sqrt{k+1}}{2}$ . Putting this in above equation, we get
$\begin{align} u_k > \frac{3\sqrt{k+1}}{4} + \frac{\sqrt{9k-7}}{4}. \label{1} \end{align}$
Claim: For any integer $k > 1$ , we have
$\frac{3\sqrt{k+1}}{4} + \frac{\sqrt{9k-7}}{4} > \frac{3\sqrt{k}}{2}.$
Proof: This is mere algebra. Just work backwards a bit to get that the claim is true iff
$\sqrt{9k+9} + \sqrt{9k-7} > 6\sqrt{k}$ Since everything positive, squaring both sides and simplifying a bit we would get
$\sqrt{(9k+9)(9k-7)} > 9k-1$ Simplifying this more would give you $k > \frac{16}{9}$ as desired. $\square$

Using this claim in $(1)$ , we would get $u_k > \frac{3\sqrt{k}}{2}$ which is a contradiction to the induction hypothesis. This completes the solution. $\blacksquare$

This post has been edited 2 times. Last edited by SatisfiedMagma, May 20, 2023, 12:05 PM
Reason: still nothing

Z K Y

The post below has been deleted. Click to close.

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

925 posts

#8 h Jun 7, 2023, 7:43 PM • 5 Y

Y by MathsSolver007, kamatadu, maths_arka, Commander_Anta78, chakrabortyahan

Note that $\star \le u_n \le \frac{3}{2}\sqrt{n}$ can be written as $(u_n - \star) \left(u_n -\frac{3}{2}\sqrt{n}\right)\le 0$ which rearranges to the following: $u_n + \frac{\star \frac{3}{2}\sqrt{n}}{u_n} \le \star + \frac{3}{2}\sqrt{n}.$ By setting $\star$ to be the reciprocal of $\frac{3}{2}\sqrt{n}$ (which holds for $n\ge 2$ since $u_n\ge 1$ ), the above LHS becomes $u_{n+1}$ and the RHS is $\frac{2}{3\sqrt{n}} + \frac{3}{2}\sqrt{n}$ which can be shown to be less than $\frac{3}{2}\sqrt{n+1}$ , completing the induction step for $n\ge 2$ . Therefore induction completes the proof.

More details: Note that $\frac{2}{3\sqrt{n}} \le \frac{3}{2} \left(\sqrt{n+1} - \sqrt{n}\right)=\frac{3}{2} \frac{1}{\sqrt{n+1}+\sqrt{n}}$ is equivalent to $\left(1+\frac{1}{n}\right)^{1/2} \le \frac{9}{4}-1 =\frac{5}{4}$ . This holds for $n\ge 2$ , because $\left(1+\frac{1}{n}\right)^{1/2} \le \sqrt{\frac{3}{2}} \le \frac{5}{4}.$

This post has been edited 4 times. Last edited by Ghoshadi, Jun 7, 2023, 7:50 PM
Reason: Added more details

Z K Y

The post below has been deleted. Click to close.

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

lifeismathematics

1188 posts

lifeismathematics

#10 h Jul 13, 2023, 2:10 PM

Y by

first of all we express $u_{n}$ in terms of $u_{n+1}$ we get $u_{n}=\frac{u_{n+1}^2+\sqrt{u_{n+1}-4}}{2}$ , as since $x+\frac{1}{x}$ is an increasing function $\forall$ $x>0$ , hence $u_{n}$ is increasing and we ignore the negative case.

now we claim that the given statement is true $\forall$ $n \geqslant 2$ and case of $n=1$ trivially holds, we will show by induction on $n$ .

Base Case:- we observe that $u_{2}=2 \leqslant \frac{3\sqrt{2}}{2}$

so base case trivially works.

Now assume that the given inequality holds for case of $n$ .

we observe the case of $n+1$ ,

Observe: $\frac{u_{n+1}+\sqrt{u_{n+1}^2-4}}{2}=u_{n} \leqslant \frac{3\sqrt{n}}{2}$

so we get $\frac{3\sqrt{n+1}}{2} \geqslant \frac{4+9n}{6\sqrt{n}} \geqslant u_{n+1}$

which is trivially true $\forall$ $n \geqslant 2$ , hence from induction hypothesis we have the given inequality to be true i.e. $u_{n} \leqslant \frac{3\sqrt{n}}{2}$ . $\blacksquare$

This post has been edited 2 times. Last edited by lifeismathematics, Jul 13, 2023, 3:18 PM

Z K Y

The post below has been deleted. Click to close.

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

maths_enthusiast_0001

133 posts

maths_enthusiast_0001

#11 h Aug 31, 2024, 6:46 PM

Y by

We will use induction.
Let $P(n)$ be the statement that $u_n \le \frac{3\sqrt{n}}{2}$ for all $n \geq 1$ .
Base Case: It is easy to see that it holds for $n=1,2$ .
Inductive Step: Assume that $P(n)$ is true.
Claim: $P(n+1)$ is true.
Proof: Clearly $f(x)=x+\dfrac{1}{x}$ is an increasing function for $x >1$ . So we have,
$u_{n+1}=u_{n}+\dfrac{1}{u_{n}} \leq \frac{3\sqrt{n}}{2}+\frac{2}{3\sqrt{n}}$ Claim: If $n \geq \dfrac{16}{9}$ then, $\frac{3\sqrt{n}}{2}+\frac{2}{3\sqrt{n}} \leq \frac{3\sqrt{n+1}}{2}$
Proof: The above statement can be rewritten as, $\iff \frac{2}{3\sqrt{n}} \leq \dfrac{3}{2}\dfrac{1}{\sqrt{n}+\sqrt{n+1}}$ $\iff \dfrac{4}{9} \leq \dfrac{\sqrt{n}}{\sqrt{n}+\sqrt{n+1}}$ $\iff 4\sqrt{n+1} \leq 5\sqrt{n} \iff n \geq \dfrac{16}{9}$ .
Thus we have proved that $u_{n} \leq \dfrac{3\sqrt{n}}{2}$ for all $n \geq 2$ and separately for $n=1$ . (QED) $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

85 posts

#12 h Jan 1, 2025, 11:45 PM

Y by

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ

This post has been edited 1 time. Last edited by mqoi_KOLA, Apr 15, 2025, 9:44 AM

Z K Y

The post below has been deleted. Click to close.

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

478 posts

#13 h Apr 15, 2025, 9:57 AM

Y by

No bash. Clean solution.

Note that $u_1\le \frac{3}{2}\sqrt{1}$ .

Also, $u_2=u_1+\frac{1}{u_1}>0$ . Similarly, if $u_i>0$ , then $u_{i+1}=u_i +\frac{1}{u_i}>0$ . So $u_1>0\implies u_2>0 \implies \cdots$ and so on. This gives us that $u_i>0$ for all $i\ge 1$ .

Now note that for all $n\ge 2$ , by AM-GM we get that,
$u_n = u_{n-1}+\frac{1}{u_{n-1}}\ge 2 .$
Claim: $u_n \le \frac{3}{2}\sqrt{n}$ for all $n\ge 2$ .
Proof:We proceed by using induction on $n$ .

Base Case: For $n=2$ , $u_2 = 2 \le \frac{3}{2}\sqrt{2}$ .
Induction Hypothesis: Assume that our claim is true for some $n=k\ge 2$ .
Inductive Step: We prove the claim for $n=k+1$ .
$\begin{align*} u_{k+1}^2 &= u_k^2+\frac{1}{u_k^2}+2\\ &\le \frac{9k}{4}+\frac{1}{2}+2\\ &= \frac{9(k+1)}{4} .\end{align*}$
This gives us that $a_{k+1}\le \frac{3}{2}\sqrt{k+1}$ and thus our induction is complete.

Hence with the proof of our claim and the case $n=1$ , the problem is solved.

This post has been edited 1 time. Last edited by kamatadu, Apr 15, 2025, 9:58 AM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a