Given a natural number $n\ge 3$, determine all strictly increasing sequences $a_1<a_2<\cdots<a_n$ such that $\text{gcd}(a_1,a_2)=1$ and for any pair of natural numbers $(k,m)$ satisfy $n\ge m\ge 3$, $m\ge k$, $$\frac{a_1+a_2+\cdots +a_m}{a_k}$$ is a positive integer.
Problem
Source: Junior Olympiad of Malaysia Shortlist 2015 N3 (JOM P4)
Tags: number theory
18.07.2015 14:18
My solution: Claim: The answer is the sequence $a_i$ such that $a_1=1, a_2=2, a_3=3$ and for $4\le i\le n$ we have $a_i=3\times 2^{I-3}$. We prove the claim by induction on $n$. First assume that $n=3$ from the condition: $ a_2\mid a_1+a_2+a_3$(1) and $ a_3\mid a_1+a_2+a_3$ now note that: $a_3\mid a_1+a_2+a_3\longrightarrow a_3\mid a_1+a_2\longrightarrow a_3t=a_1+a_2<2a_3$ so $t=1$ and $a_3=a_1+a_2$(2) hence from (1), (2) we get $a_2\mid 2 (a_1+a_2)\longrightarrow a_2\mid 2a_1$ since $\text{gcd} (a_1, a_2)=1$ we get $a_2\mid 2$ so because $a_2\ge a_1+1\ge 2$ we get $a_1=1, a_2=2$ and from (2): $a_3=3$. Now assume that the claim is true for $n$. Now we want to prove it for $n+1$. Assume that the sequence $a_1<a_2 <\dots <a_{n+1}$ satisfy the condition of the problem. So the sequence $a_1 <a_2 <\dots <a_n$ satisfy the condition hence from induction assumption we get $a_1=1, a_2=2, a_3=3$ and for $4\le i\le n$ we have $a_i=3\times 2^{i-3}$ it is easy to see that $a_n=a_1+a_2+\dots +a_{n-1}$ now from the condition we have $a_{n+1}\mid a_1+a_2+\dots+a_n=2a_n$(3) and $a_n\mid a_1+\dots +a_{n+1}=2a_n+a_{n+1}\longrightarrow a_n\mid a_{n+1}\longrightarrow a_{n+1}=a_ns$ from (3) and using the fact that $a_{n+1}> a_n$ we get $a_{n+1}=2a_n $ and the claim proved hear. DONE