In an infinite increasing sequence of positive integers, every term from the $2002^{\text{th}}$ term divides the sum of all preceding terms. Prove that every term starting from some term is equal to the sum of all preceding terms.
Problem
Source: Tournament of Towns,Spring 2002, Junior A Level, P6
Tags: induction, inequalities, number theory proposed, number theory
BISHAL_DEB
14.05.2014 15:37
It is easy to show that once a term becomes the sum of all the previous terms the property is also obeyed by all the following terms. Let $S$ be the sum of the first 2001 terms. If $T_i$ denotes the $i$th term then assuming the contrary gives $T_{2002}\leq S/2$. Proceeding by induction we have $T_{2001+i}\leq (1-1/2^i)\times S$ which goes against the fact that the sequence is infinite and increasing.
mathuz
17.05.2014 02:34
let $ (a_n)_{n\ge 1} $ be the sequence. Then we have a sequence of positive integers $(s_n)_{n\ge 2002} $ such that \[ s_n=\frac{a_1+a_2+...+a_{n-1}}{a_n}. \] We get that $ s_{n+1}=\frac{a_n}{a_{n+1}}(s_n+1)<s_n+1 $ for all $n\ge 2002$. So we can $ s_{n+1}\le s_n \le ...\le s_{2002} $. We are done!
2015WOOTer
22.02.2015 22:11
For the sake of brevity, let $s_n=a_1+\ldots +a_{n-1}$. We will first prove a lemma.
Lemma: $\dfrac{s_{n-1}}{a_n}>\dfrac{s_n}{a_{n+1}}$.
Proof: Cross multiplying, we find that our claim is equivalent to \[(a_{n+1}-a_n)(a_1+\ldots+a_{n-1})>a_n^2. \]Since $a_n$ divides $s_{n-1}$, $s_{n-1}$ may be expressed in the form $ka_n$, for some $k\in\mathbb{N}$. Also, $\dfrac{s_{n}}{a_{n+1}}=\dfrac{(k+1)a_n}{a_{n+1}}=l$, for some $l\in\mathbb{N}$ as well. From this, we can clearly see that $k+1\ge 2l$, as $a_n+1\le a_{n+1}$. Substituting these expressions into our inequality, we find that \[\left(\left(\dfrac{k+1}{l}-1\right)a_n\right)(ka_n)=\left(\dfrac{k(k-l+1)}{l}\right)a_n^2>a_n^2, \]which is clearly true. The lemma is proved.
End Lemma
Using the lemma, we see that $x_n=\dfrac{s_{n-1}}{a_n}$ is a sequence of strictly decreasing positive integers, so $x_n$ must converge to $1$ for some large $n$. It is easy to see that for all $n_0>n$, $x_{n_0}$ will also equal $1$. Hence, $s_{n}=a_{n+1}$ for infinitely many $n$, and we are done.
Mogmog8
04.10.2021 06:11
Let our sequence be $a_1,a_2,\dots$ and $s_n=\sum_{i=1}^{n}{a_i}.$ We know if $n>2002,$ $s_n=a_{n+1}b_{n+1}$ and $s_{n-1}=a_nb_n$ where $b_i$ are positive integers. Subtracting, we have $$s_n-s_{n-1}=a_n=a_{n+1}b_{n+1}-a_nb_n,$$or $\frac{b_{n+1}}{b_n+1}=\frac{a_n}{a_{n+1}}<1.$ Thus, $b_{n+1}\le b_n,$ meaning that for some $m,$ $b_m=b_{m+1}=\dots.$ Then, $$a_m=b_m(a_{m+1}-a_m),\quad(*)$$which implies that $a_{m+1}-a_m\mid a_m.$ But if we add $a_mb_m$ to $(*),$ we have $a_m(b_m+1)=a_{m+1},$ so $a_m\mid a_{m+1},$ which means that $a_m\mid a_{m+1}-a_m.$ Hence, $a_{m+1}-a_m=a_m,$ or $a_{m+1}=2a_m.$ Substituting into $(*),$ we have $b_m=1,$ meaning that $a_m=s_{m-1},a_{m+1}=s_m\dots$ for some $m.$ $\square$
HamstPan38825
23.07.2022 05:31
Let $\{a_n\}$ be the sequence. By the condition, there exists a constant $k_i$ for every $i$ such that $$a_1+a_2+\cdots+a_{n-1} = k_na_n$$for all $n \geq 2002$. We may write $$k_{n+1} = \frac {a_n}{a_{n+1}} (k_n + 1) < k_n+1.$$In particular, $\{k_n\}$ is strictly nonincreasing, so there exists $N \geq 2002$ such that $\{k_n\}$ is constant for all $n \geq N$. Thus, for these $n$, we also have $$k_Na_{n+1} =a_n(k_N+1).$$In particular, $k_N \mid a_n$ for all $n \geq N$, so we may construct an infinite descent unless $k_N = 1$. Then, $$a_1+a_2+\cdots+a_{n-1} = a_n$$for these $n \geq N$, as required.