This sequence looks familiar

Relevant wiki: Strong Induction

Exploring this sequence, you would find that this sequence is actually just triangular numbers. Let's try and prove that $a_n = 0 + 1 + 2 + \ldots + (n-1)$ via strong induction.

The base case, $n=1$ is already given.

For the inductive part, assume $a_n = 0 + 1 + 2 + 3 + \cdots + (n-1)$ for $n \leq k$ . We know

$a_{k+1} = \displaystyle \max_{i=1,2,\ldots,k} \{i + a_i + a_{k+1-i}\} \quad (1)$

We claim that the max in $(1)$ occurs when $i=k$ . For this, it is sufficient to prove that whenever $i < k$ , we have

$k + a_k + a_1 > i + a_i + a_{k+1-i}$

But since $a_1 = 0$ and $k>i$ , it suffices to show

$a_k - a_i \geq a_{k+i-1}$

Using the inductive assumption, we have

$\begin{aligned} a_k - a_i &= (0 + 1 + 2 + \ldots + (k-1)) - (0 + 1 + 2 + \ldots + (i-1))\\ &= i + (i+1) + \cdots + (k-1) \quad (2)\\ \end{aligned}$

and

$\begin{aligned} a_{k+1-i} &= 0 + 1 + 2 + \cdots + (k-i)\\ &= 1+ 2+ \cdots + (k-i) \quad (3)\\ \end{aligned}$

Observe that both RHS of $(2)$ and $(3)$ consist of $k-i$ consecutive terms. Since the first term in $(2)$ must be at least as big as $(3)$ , our claim must hold true.

Therefore, we have

$\begin{aligned} a_{k+1} &= \displaystyle \max_{i=1,2,\ldots,k} \{i + a_i + a_{k+1-i}\}\\ &= k + a_k + a_1\\ &= k + (0 + 1 + 2 + \ldots + (k-1)) + 0\\ &= 0 + 1 + 2 + \cdots + k\\ \end{aligned}$

This completes our induction.

Now we can apply the well-known triangular numbers formula $a_n = \frac {n(n-1)}{2}$ to get

$a_{200} = \dfrac{200 \times 199}{2} = \boxed{19900}.$

Claim : $a_k = \tfrac12 k(k-1)$ .

Proof : The claim is obviously true for $k = 1$ .

Suppose the claim is true for all $k \leq n$ . Let $1 \leq i \leq n$ , and $z = i - \tfrac12(n+1)$ . Then $i + a_i + a_{n+1-i} = \tfrac12(n+1) + z + \tfrac12 (\tfrac12(n+1) - z)(\tfrac12(n+1) - z - 1) + \tfrac12 (\tfrac12(n+1) + z)(\tfrac12(n+1) + z - 1) \\ = \tfrac14n^2 + \tfrac12n + (z+\tfrac12)^2,$ which is maximal when $|z + \tfrac12|$ is greatest; this happens for $i = n$ , with $z = \tfrac12(n-1)$ .

The recursion reduces to $a_{n+1} = \tfrac14n^2 + \tfrac12n + (\tfrac12n)^2 = \tfrac12n(n+1),$ showing that the claim also holds for $k = n+1$ . This finishes the induction.