Problem: Let $a_1, a_2, a_3, \dots$ be a sequence of positive real numbers, and $s$ be a positive integer, such that
\[
  a_n =
  \max \{ a_k + a_{n-k} \mid 1 \leq k \leq n-1 \}
  \text{ for all $n > s$}.
\]
Prove there exist positive integers $\ell \leq s$ and $N$, such that
\[
  a_n =
  a_{\ell} + a_{n - \ell} \text{ for all $n \ge N$}.
\]

\end{enumerate}

Solution: Let \[ w_1 = \frac{a_1}{1}, \quad w_2 = \frac{a_2}{2},
    \quad \dots, \quad w_s = \frac{a_s}{s}. \]
(The choice of the letter $w$ is for ``weight''.)
We claim the right choice of $\ell$
is the one maximizing $w_\ell$.

Our plan is to view each $a_n$ as a linear combination
of the weights $w_1, \dots, w_s$ and track their coefficients.

To this end, let's define an \emph{$n$-type}
to be a vector $T = \left< t_1, \dots, t_s\right>$
of nonnegative integers such that
\begin{itemize}
  \ii $n = t_1 + \dots + t_s$; and
  \ii $t_i$ is divisible by $i$ for every $i$.
\end{itemize}
We then define its \emph{valuation} as $v(T) = \sum_{i=1}^s w_i t_i$.

Now we define a $n$-type to be \emph{valid}
according to the following recursive rule.
For $1 \le n \le s$ the only valid $n$-types are
\begin{align*}
  T_1 &= \left< 1, 0, 0, \dots, 0 \right> \\
  T_2 &= \left< 0, 2, 0, \dots, 0 \right> \\
  T_3 &= \left< 0, 0, 3, \dots, 0 \right> \\
  &\vdotswithin= \\
  T_s &= \left< 0, 0, 0, \dots, s \right>
\end{align*}
for $n = 1, \dots, s$, respectively.
Then for any $n > s$, an $n$-type is valid
if it can be written as the sum of a valid $k$-type
and a valid $(n-k)$-type, componentwise.
These represent the linear combinations possible in the recursion;
in other words the recursion in the problem is phrased as
\[ a_n = \max_{T \text{ is a valid $n$-type}} v(T). \]

In fact, we have the following description of valid $n$-types:
\begin{claim*}
  Assume $n > s$.
  Then an $n$-type $\left< t_1, \dots, t_s \right>$ is valid
  if and only if either
  \begin{itemize}
    \ii there exist indices $i < j$ with $i+j > s$,
    $t_i \ge i$ and $t_j \ge j$; or
    \ii there exists an index $i > s/2$
    with $t_i \ge 2i$.
  \end{itemize}
\end{claim*}
\begin{proof}
  Immediate by forwards induction on $n > s$
  that all $n$-types have this property.

  The reverse direction is by downwards induction on $n$.
  Indeed if $\sum_i \frac{t_i}{i} > 2$,
  then we may subtract off on of $\{T_1, \dots, T_s\}$
  while preserving the condition;
  and the case $\sum_i \frac{t_i}{i} = 2$
  is essentially by definition.
\end{proof}
\begin{remark*}
  The claim is a bit confusingly stated in its two cases;
  really the latter case should be thought of as the situation
  $i=j$ but requiring that $t_i/i$ is counted with multiplicity.
\end{remark*}

Now, for each $n > s$ we pick a valid $n$-type $T_n$
with $a_n = v(T_n)$;
if there are ties, we pick one for which the $\ell$th
entry is as large as possible.
\begin{claim*}
  For any $n > s$ and index $i \neq \ell$,
  the $i$th entry of $T_n$
  is at most $2s + \ell i$.
\end{claim*}
\begin{proof}
  If not, we can go back $i\ell$ steps to get
  a valid $(n-i\ell)$-type $T$
  achieved by decreasing the $i$th entry of $T_n$ by $i \ell$.
  But then we can add $\ell$ to the $\ell$th entry $i$
  times to get another $n$-type $T'$ which obviously
  has valuation at least as large,
  but with larger $\ell$th entry.
\end{proof}

Now since all other entries in $T_n$ are bounded,
eventually the sequence $(T_n)_{n > s}$
just consists of repeatedly
adding $1$ to the $\ell$th entry, as required.

\begin{remark*}
One big step is to consider $w_k = a_k / k$.
You can get this using wishful thinking
or by examining small cases.
(In addition this normalization makes it easier
to see why the largest $w$ plays an important role,
since then in the definition of type,
the $n$-types all have a sum of $n$.
Unfortunately, it makes the characterization
of valid $n$-types somewhat clumsier too.)
\end{remark*}