For two rational numbers $r,s$ we say:$$r\mid s$$whenever there exists $k\in\mathbb{Z}$ such that:$$s=kr$$${(a_n)}_{n\in\mathbb{N}}$ is an increasing sequence of pairwise coprime natural numbers and ${(b_n)}_{n\in\mathbb{N}}$ is a sequence of distinct natural numbers. Assume that for all $n\in\mathbb{N}$ we have: $$\sum_{i=1}^{n}\frac{1}{a_i}\mid\sum_{i=1}^{n}\frac{1}{b_i}$$Prove that for all $n\in\mathbb{N}$ we have: $a_n=b_n$.
Problem
Source: Iran MO Third Round N2
Tags: number theory, Divisibility, Sequence
Shayan-TayefehIR
08.09.2022 12:30
Hints
First idea : by working on some trivial inequalities , take $a_1=b_1$ and $a_2=b_2$ and then use induction on $n$
Second idea : for each $n \in \mathbb{N}$ , define $k_n$ such below :
$$k_n \sum_{i\le n}{\frac{1}{a_i}}=\sum_{i\le n}{\frac{1}{b_i}}$$Then prove that $k_n$ is descending and eventually becomes $1$ and for each large enough $n$ , we have $a_n=b_n$.
Mehrshad
16.09.2022 14:17
@Shayan-TayefehIR Can you explain the first idea in more detail?
JG666
05.02.2023 05:09
Would you please post the official solution? @Mehrshad Thanks!
shinhue
06.06.2023 15:31
Bump this !!
Mahdi_Mashayekhi
06.06.2023 16:36
Assume that $\sum_{i=1}^{n}\frac{1}{b_i} = k_n\sum_{i=1}^{n}\frac{1}{a_i}$. Now we have $:$
$$\frac{1}{b_{n+1}} = \sum_{i=1}^{n+1}\frac{1}{b_i} -\sum_{i=1}^{n}\frac{1}{b_i} = k_{n+1}\frac{1}{a_{n+1}}+(k_{n+1}-k_n)\sum_{i=1}^{n}\frac{1}{a_i}$$Now choose $m$ large enough such that for $n > m$ we would have $b_n > a_0$. This implies that $\frac{1}{b_{n+1}} < \sum_{i=1}^{n}\frac{1}{a_i}$ which implies $k_{n+1} \le k_n$. Since $k_i \in \mathbb{N}$ we have that eventually $k_n$ becomes constant which implies $a_{n+1} = kb_{n+1}$ and since ${(a_n)}_{n\in\mathbb{N}}$ is an sequence of pairwise coprime natural numbers we have that $k = 1$ so there exists $N$ such that $\forall n>N$ we have $a_n = b_n$. it's clear that $k_N = 1$. Now note that
$$ \frac{1}{b_N} = \frac{1}{a_N} + (1-k_{N-1})\sum_{i=1}^{N-1}\frac{1}{a_i}$$Since ${(a_n)}_{n\in\mathbb{N}}$ is an increasing sequence of numbers then if $k_{N-1} \neq 1$ then RHS becomes negative which gives contradiction so $k_{N-1} = 1$ and $a_N = b_N$. Now using induction will finish the problem.