Let $(a_n)$ be sequnce of positive integers such that first $k$ members $a_1,a_2,...,a_k$ are distinct positive integers, and for each $n>k$, number $a_n$ is the smallest positive integer that can't be represented as a sum of several (possibly one) of the numbers $a_1,a_2,...,a_{n-1}$. Prove that $a_n=2a_{n-1}$ for all sufficently large $n$.
Problem
Source: IZHO 2017 day 2 p4
Tags: algebra, number theory, Integer sequence, Sequence
15.01.2017 16:12
Consider the numbers $a_1<a_2<\cdots a_k$, we let a few more terms to fill up the numbers from $1$ to $a_k$, untill eventually a term $a_{m+1}$ is greater than $a_k$. At this point every number from $1$ to $a_k>a_m$ is sum of several numbers in $a_1$ to $a_k$. So WLOG that the initial set of numbers $a_1,\cdots a_k$ are such that every number from $1$ to $a_k$ is sum of several from $a_1,\cdots,a_k$. Consider the expression $x_n=a_1+\cdots+a_n$ for every $n\ge k$, clearly $x_n$ is the largest number than is the sum of several of $a_1,\cdots, a_n$. So $x_n+1$ is not representable by sum of a several of $a_1,\cdots a_n$, so $a_{n+1}\le x_n+1$. On the other hand, since every number from $1$ to $a_{n+1}-1$ is sum of several of $a_1,\cdots, a_n$, then every number from $1$ to $2a_{n+1}-1$ is sum of several of $a_1,\cdots, a_{n+1}$. So $a_{n+2}\ge 2a_{n+1}$, and so $$x_n-a_{n+1}=x_{n+1}-2a_{n+1}\ge x_{n+1}-a_{n+2}$$That is the difference $x_{n+1}-a_{n+2}$ is non increasing. So since its a integer sequence at least $-1$, it is eventually constant. Take such $M$ such that $x_{n+1}-a_{n+2}=x_{n}-a_{n+1}$ for all $n>M$, then $a_{n+2}=x_{n+1}-x_n-+a_{n+1}=2a_{n+1}$ for all $n>M$, as desired.
15.01.2017 18:35
My solution: Let $S_r$ be set of numbers that we can get from numbers $a_1,...,a_r$ that is all sums of several of them. Let $b_r$ be number of positive integer $x$ such that $x\le max S_r$ and $x$ can't be represented as sum of several $a_i$'s for $i\le r$. ______________________ Lemma 1: $b_{n}=b_{n-1}-x$ where $x$ is number of $c_i$ not in $1,2,...,2a_n-1$,for $n>m$ where $m$ is the first number such that $a_m>max(a_i,i\le k)$. Proof: We have that $S_{n-1}=(1,2,...,a_{n}-1,c_{1},...,c_{j})$ for some $c_i$ such that $c_i>a_n$ and let WLOG $c_j$ be maximums $c_i$. Since $S_n=(1,2,...,2a_n-1)\cup (c_1,...,c_j)\cup (c_1+a_n,...,c_j+a_n)$. In $S_{n-1}$ we could achieve $j+a_n-1$ numbers so we can't achieve $c_j-a_n-j+1=b_{n-1}$. In $S_n$ we can achieve at least $| (1,2,...,2a_n-1)\cup (c_1,...,c_j)\cup (c_1+a_n,...,c_j+a_n)|= |(1,2,...,2a_n-1)\cup (c_1,...,c_j)| + |(c_1+a_n,...,c_j+a_n)|=2a_n-1+x+j$. So we can't achieve $b_n=c_j+a_n-2a_n+1-x-j=b_{n-1}-x$. _____________________ Lemma 2: If $b_{n-1}=b_{n}$ then $a_{n+1}=2a_n$. Proof: We have that $b_{n}\le b_{n-1}-x$(from lemma 1) but since $b_n=b_{n-1}$ we have that $x=0$ so $2a_{n}$ is not in $S_n$ because $c_i+a_n>2a_n$ and $c_i=2a_n-t$ for $t>0$. It implies that $a_{n+1}=2a_n$. ___________________________ Let $a_m$ be defined as in lemma 1. We have from lemma 1 that $b_n$ is decreasing but since it's integer since it must become constant at some $n=N$. Now applying lemma 2 for $n>N$ we have that $a_n=2a_{n-1}$ for all $n>N$.
24.05.2017 03:11
Lemma 1: $a_{n+1}\geq 2 a_{n},\, n>k$, in particular $a_n$ is eventually increasing and unbounded: $a_n\geq 2^{n-k-1}a_{k+1}$. Every number $\{1,2, \ldots, a_{n}-1\}$ is a sum of some of $\{1,2, \ldots, a_{n-1}\}$, hence $\{1,2, \ldots, 2a_{n}-1\}$ are sums of some of $\{1,2, \ldots, a_{n}\}$. Lemma 2: $a_{n+1}\leq 2 a_{n}+r,\, n>k$, where $r=1+a_1+\ldots+a_k$. $a_{n+1}\leq a_1+\ldots +a_n+1\leq r+\ldots+a_n/4+a_n/2+a_n\leq r+2 a_n.$ Lemma 3: $a_1+\ldots+a_{n}<4 a_n$ for all sufficiently large $n$. For large $n$, we have $4 a_n\geq 2 a_{n}+2^{n-k-1}a_{k+1}>2 a_n+r\geq a_1+\ldots+ a_{n}.$ Lemma 4: Let $n\geq M$ s.t. above lemmas hold: if $a_{m+1}=2a_{m}$ for some $m>M$ then $a_{n+1}=2a_{n}$ for all $n\geq m.$ If $a_{m+1}=2a_{m}$ then $2a_m$ is not a sum of any of $a_1,\ldots a_m$, also from lemma 3, $2a_{m+1}=4a_m$ is not a sum of any of $a_1,\ldots a_m$, hence $2a_{m+1}=4a_m$ is not a sum of any of $a_1,\ldots a_m, a_{m+1}=2 a_m$, thus $a_{m+2}\leq 2 a_{m+1}$ then by Lemma 1 $a_{m+2}=2 a_{m+1}$. The claim follows by induction. It remains to prove $a_{m+1}<2a_{m}+1$ for some $m\geq M$. Assume the contrary: $a_{n+1}\geq 2a_{n}+1, \forall n\geq M$, then $a_i\leq a_N/2^{N-i}- \frac 1 2,\, i\geq M$ so $a_M+\ldots+a_N\leq a_N+a_N/2+\ldots -(N-M)/2\leq 2a_N -(N-M)/2$ and $a_{N+1}\leq 1+a_1+\ldots a_N\leq 2a_N +1+a_1+\ldots+a_{M-1}-(N-M)/2<2a_N$ for large $N$, which contradicts lemma 2.
13.07.2017 17:05
Similar to above, but anyway,
03.01.2020 03:15
Denote by $S_n$ the sum of the first $n$ terms. It is easy to see that $a_{n+1}\geq 2a_n$ for $n\geq k+1$ and $a_{n+1}\leq S_n+1$ for $n\geq k$. Now define $d_n:=a_{n+1}-S_n$. Obviously $d_n$ is an integer. From the second inequality, we have that $\{d_n\}_{n\geq k}$ is bounded from above by the constant $1$. We shall verify that $\{d_n\}_{n\geq k}$ is increasing. Indeed, $d_{n+1}\geq d_n \iff a_{n+2}-S_{n+1} \geq a_{n+1}-S_n$ $\iff a_{n+2}\geq 2a_{n+1}, $ which is true. Now there must exist some constant $c,$ such that $d_n=d_{n+1}=d_{n+2}=\cdots$ for all $n\geq c,$ from where we obtain $d_{n+1}=d_n \iff a_{n+2}-S_{n+1}=a_{n+1}-S_n \iff a_{n+2}=2a_{n+1},$ which was to be shown. $\blacksquare$