Base case $n=3$ trivial. Assume $n>3$. For the construction, I claim that we can reach the required sum by starting with the cycle $$\cdots -7-5-3-1-2-4-6-8-\cdots$$ (this closes on the other end by $n, n-1$ in some order). Delete 1 and sum. This yields $$\cdots -(7+5)-(5+3)-(3+2)-(2+4)-(4+6)-(6+8)-\cdots$$ The numbers in this cycle can be seen to be in the same configuration with respect to their order as in the original cycle, so by the induction hypothesis, we can get to the required sum for the new numbers. A calculation shows this is equal to the required sum for the old numbers. To prove this is optimal, we can assume $a_1$ was deleted at first (otherwise replace whatever was deleted by $a_1$, and this only increases the result). After the deletion, we get sums $a_i+a_j$ in a circle so that the graph on $n-1$ vertices resulting from joining $i\leftrightarrow j$ if they appear in the same sum is a cycle. By the induction hypothesis, this is at most the sum $$(1)\qquad\sum_{k=1}^{n-1}\binom{n-3}{[k/2]-1} (\cdots)$$ where $(\cdots)$ is each time one of the sums $a_i+a_j$ in the circle. We want to prove that this is at most $$(2)\qquad \sum_{k=1}^n \binom{n-2}{[k/2]-1} a_k$$ For this, we use a well known lemma: LemmaSuppose $a_1\leq a_2\leq \cdots \leq a_n$. Let $x_i, y_i$ be real numbers satisfying $$\forall 1\leq i\leq n: x_i+x_{i+1}+\cdots+x_n\geq y_i+y_{i+1}+\cdots+y_n$$ $$x_1+\cdots+x_n=y_1+\cdots+y_n$$ Then the inequality $$x_1a_1+x_2a_2+\cdots+x_na_n\geq y_1a_1+\cdots+y_na_n$$ is satisfied. We'll use the lemma for $x_k=\binom{n-2}{[k/2]-1}$ and $y_k$ the coefficient of $a_k$ in $(1)$, for $k\geq 2$ (as $a_1$ does not appear). First, $\sum_{i=2}^n y_i$ is twice the sum of the binomial coefficients in $(1)$. By $$(*)\qquad x_k=\binom{n-2}{[k/2]-1}=\binom{n-3}{[k/2]-1}+\binom{n-3}{[(k-2)/2]-1}$$ when we sum the $x_k$ we'll get twice every binomial coefficient in $(1)$, but with an addition of a term for $k=n$, and the term for $k=n-1$ only appearing once. But these two terms are equal: $$\binom{n-3}{[n/2]-1}=\binom{n-3}{[(n-1)/2]-1}$$ as the sum of the lower numbers is exactly $n-3$. Thus we get each coefficient twice which is exactly the sum of the $y_i$. We now prove that for $2\leq k\leq n$ we have $$x_{k+1}+\cdots+x_n\geq y_{k+1}+\cdots+y_n$$ Let's understand the right sum. It is a sum of $n-k$ pairs of binomial coefficients appearing in $(1)$ (as each $y_i$ is a sum of binomial coefficients). But each coefficient appears at most twice in the sum. Thus the sum is at most $$\sum_{j=k+1}^n y_j\leq 2\sum_{i=k}^{n-1}\binom{n-3}{[i/2]-1}$$ which is twice the sum of the $n-k$ largest coefficients in $(1)$. I claim that in fact $$\sum_{j=k+1}^n y_j < 2\sum_{i=k}^{n-1}\binom{n-3}{[i/2]-1}$$ Indeed, if equality holds, then for each $k$ the $(\cdots)$ in $(1)$ at the $k$-th position is $a_i+a_j$ for $i,j\geq k+1$ (so these coefficients only go to $y_i$ for $i\geq k+1$). But then the resulting graph would not be a cycle because the subgraph consisting of $i\geq k+1$ would have all degrees 2. Contradiction. This implies that $\sum_{j=k+1}^n y_i$ is a sum of pairs of binomial coefficients, each appearing in the sum at most twice, which is less than the maximal possible such sum. Thus we must have $$\sum_{j=k+1}^n y_j\leq \binom{n-3}{[(k-1)/2]-1}+\binom{n-3}{[k/2]-1}+2\sum_{i=k+1}^{n-1}\binom{n-3}{[i/2]-1}$$ which is equal to $\sum_{j=k+1}^n x_k$ by $(*)$. This finishes the proof.