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 5 of 9: The normalized sequence obeys the same recurrence

Previous step Next step

b_n=\max_{1\le k\le n-1}(b_k+b_{n-k})

Detailed analysis

For $n>s$ , subtracting $qn$ from the original recurrence gives $b_n=\max_{1\le k\le n-1}(b_k+b_{n-k})$ , because $qk+q(n-k)=qn$ . Together with the initial values, this recurrence also gives an expansion of every $b_n$ as a sum of terms $b_i$ with $i\le s$ .