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 6 of 9: Bound the normalized values

Previous step Next step

-M\le b_n\le0,\qquad M=\max_{1\le i\le s}(-b_i)

Detailed analysis

If all $b_1,\ldots,b_s$ are zero, the recurrence gives $b_n=0$ for every $n$ , and the conclusion follows immediately from $a_n=qn$ and $a_\ell=q\ell$ . Otherwise set $M=\max_{1\le i\le s}(-b_i)$ and $\varepsilon=\min\{-b_i:b_i<0\}>0$ . Since the split $n=\ell+(n-\ell)$ is allowed, $b_n\ge b_{n-\ell}$ ; iterating this reaches an initial index and proves $-M\le b_n\le0$ . Every expansion of $b_n$ therefore has at most $M/\varepsilon$ negative summands, so the values of $b_n$ belong to a finite set of sums of initial values.