Let $a_1<a_2< \cdots$ be a strictly increasing sequence of positive integers. Suppose there exist $N$ such that for all $n>N$, $$a_{n+1}\mid a_1+a_2+\cdots+a_n$$Prove that there exist $M$ such that $a_{m+1}=2a_m$ for all $m>M$. Proposed by Ivan Chan Kai Chin
Problem
Source: Own. Malaysian APMO CST 2024 P1
Tags: number theory
24.02.2024 13:34
Nice problem!! Let $a_1 + a_2 + \cdots + a_n = b_{n+1}a_{n+1}$ for all positive integers $n$. For $n>N$, we have $b_n \in \mathbb{N}$. Also, since $a_{n+1}(b_{n+1} + 1) = a_{n+2}b_{n+2}$ for all $n$, we have that $b_{n+1} + 1> b_{n+2}$ for all $n$. Hence, we have that $b_n$ is monotonouslly decreasing for $n>N$. Now, since $\lim_{k \to \infty} a_{n+k} = \infty$, we have that $\lim_{k \to \infty} \frac{a_{n+k}}{a_1 + a_2 + \cdots + a_n} = \infty$ With some calculations, we have that $$\lim_{k \to \infty}{1 + \frac{1}{b_{n+k}} + \frac{1}{b_{n+k}b_{n+k-1}}+ \cdots + \frac{1}{b_{n+k}b_{n+k-1}\cdots b_{n+1}}} = \infty$$If $b_m \ge 2$ for all $m >N$, the limit does not diverge. Hence, there exists an integer $M$ that $b_M = 1$, which implies $a_{m+1} = 2a_m$ for all $m>M$
24.02.2024 14:16
Let's define $b_n=\frac{a_1+a_2+\dots+a_n}{a_{n+1}}$ now let's look at the problem like a reccurence relation in $b_n$. We have $b_{n+1}=\frac{a_{n+1}(b_n+1)}{a_{n+2}}<b_n+1$ and since $b_n\in Z_+$ we have $b_n$ is decreasing so at some point it will be constant c Using $b_{n+1}=b_n=c$ we have $a_{n+2}=\frac{(c+1)(a_{n+1})}{c}$ and iterating gives $c^t$ divides $a_n$ (n is fixed) for any $t\in Z_+$ so $c=1$. Now it is easy to finish
24.02.2024 14:21
24.02.2024 14:48
navi_09220114 wrote: Let $a_1<a_2< \cdots$ be a strictly increasing sequence of positive integers. Suppose there exist $N$ such that for all $n>N$, $$a_{n+1}\mid a_1+a_2+\cdots+a_n$$Prove that there exist $M$ such that $a_{m+1}=2a_m$ for all $m>M$. Proposed by Ivan Chan Let $s_n \overset{\text{def}}{:=} a_1+\dots+a_n$ and $s_n = a_{n+1} \cdot b_n$, then $a_{n+2}b_{n+1} = s_{n+1}=s_n+a_{n+1} = (b_n+1) \cdot a_{n+1}$ hence $b_{n+1} = (b_n+1) \cdot \frac{a_{n+1}}{a_{n+2}}<b_n+1$. Since $(b_n)_{n>N}$ is a sequence of positive integers, with $b_{n+1} \le b_n$, there exists an integer $\ell>0$ such that $b_n=\ell$ for all sufficiently large $n$. So $\ell \cdot a_{n+2} = (\ell+1) \cdot a_{n+1}$ for all large $n$, in particular, $a_{n+1+k} = \left(\frac{\ell+1}{\ell}\right)^k \cdot a_n$ for all large $n$ and for all $k>1$, by iteration. Now if $\ell>1$, the fraction $1+\frac{1}{\ell}$ has a prime $p \ge 2$ dividing the denominator, so by raising $k$ to be a large enough exponent, $p^k \mid a_n$ for a fixed large $n$; this is a contradiction! Hence $\ell=1$ and so $a_{n+1}=2a_n$ for all large $n$, as desired.
10.03.2024 17:15
This (probably coincidentally) is the same as tournament of town junior a level spring 2002 p6 https://www.math.utoronto.ca/oz/turgor/archives/TT2002S_JAproblems.pdf
21.04.2024 18:50
Let $a_1=a_1+\ldots+a_N$ and $a_1+\ldots+a_n=a_{n+1}b_{n+1}$ Then $$b_{n+1}a_{n+1}=a_1+\ldots+a_n=a_n(b_n+1)$$for $n \geq 2$ Because $a_{n+1}>a_n$, we have $b_{n+1}<b_n+1$, thus $b$ is non-increasing. Hence it is eventually constant. Let this constant be $c$. Then for big $n$ we know $a_{n+1}=\frac{(c+1)a_n}{c}$, but if $c>1$, then $v_c(a_n)$ is non--negative and decreasing - contradiction. So $c=1$ and $a_{n+1}=2a_n$
20.06.2024 21:57
Define the sequence of positive integers $b_n=\tfrac{a_1+a_2+\dots+a_n}{a_{n+1}}$ for all ${n>N}$. Notice that we have the recursive relation $\tfrac{b_n+1}{b_{n+1}}=\tfrac{a_{n+2}}{a_{n+1}}$. Thus $\{b_n\}$ is a non-increasing sequence so must eventually be constant at $c$. However as $\{a_n\}$ is integral we must have that $\tfrac{c+1}{c}$ is also integral. Thus $c=1$ implying the result.