Problem 6

Let

a_1,a_2,a_3,\ldots

be a sequence of positive real numbers. Suppose that for some positive integer

s

, we have

a_n=\max\{a_k+a_{n-k}\mid 1\le k\le n-1\}

for all

n>s

. Prove that there exist positive integers

\ell

and

N

, with

\ell\le s

, such that

a_n=a_\ell+a_{n-\ell}

for all

n\ge N

Step 7 of 9: Each residue-class subsequence stabilizes

Previous step Next step

b_n\ge b_{n-\ell},\qquad b_{s+t},b_{s+t+\ell},b_{s+t+2\ell},\ldots

Detailed analysis

For every $n>s$ , the recurrence and $b_\ell=0$ give $b_n\ge b_{n-\ell}$ . Hence, for each $1\le t\le\ell$ , the sequence $b_{s+t},b_{s+t+\ell},b_{s+t+2\ell},\ldots$ is non-decreasing. Step 6 shows that it takes values in a finite set, so it is eventually constant. Taking the maximum of the finitely many stabilization thresholds, there is $N$ such that $b_n=b_{n-\ell}$ for every $n\ge N$ .