1. **Base Case: $n = 3$**

For $n = 3$, we have three numbers $a_1 \leq a_2 \leq a_3$. We can place them in a ring and delete one number. The remaining two numbers will be summed to give $S$. The possible sums are $a_1 + a_2$, $a_2 + a_3$, and $a_3 + a_1$. The largest sum is $a_2 + a_3$, which matches the formula:
$$S_{\text{max}} = \sum_{k=2}^3 \binom{3-2}{\left\lfloor \frac{k}{2} \right\rfloor - 1} a_k = \binom{1}{0} a_2 + \binom{1}{0} a_3 = a_2 + a_3$$

2. **Inductive Step: Assume the formula holds for $n \geq 3$**

Assume the formula holds for $n$ numbers. We need to show it holds for $n+1$ numbers.

3. **Constructing the Ring for $n+1$ Numbers**

Consider $a_1 \leq a_2 \leq \ldots \leq a_{n+1}$. Place these numbers in a ring. Delete $a_1$ (the smallest number) first. The remaining numbers form a new ring with $n$ numbers.

4. Applying the Induction Hypothesis

By the induction hypothesis, the largest sum $S$ for the remaining $n$ numbers is:
$$S_{\text{max}} = \sum_{k=2}^{n+1} \binom{n-1}{\left\lfloor \frac{k-1}{2} \right\rfloor - 1} a_k$$

5. Optimality of the Sum

To prove this is optimal, consider the sums formed after deleting $a_1$. The sums $a_i + a_j$ in the new ring form a cycle graph on $n$ vertices. By the induction hypothesis, the sum of these pairs is at most:
$$\sum_{k=1}^{n} \binom{n-2}{\left\lfloor \frac{k}{2} \right\rfloor - 1} a_k$$

6. Using the Lemma

We use the lemma to compare the coefficients of $a_k$ in the sums. Let $x_k = \binom{n-1}{\left\lfloor \frac{k-1}{2} \right\rfloor - 1}$ and $y_k$ be the coefficient of $a_k$ in the sum for $n$ numbers. We need to show:
$$\sum_{i=2}^{n+1} x_i a_i \geq \sum_{i=2}^{n+1} y_i a_i$$

7. Summing the Coefficients

The sum of the coefficients $y_i$ is twice the sum of the binomial coefficients in the induction hypothesis. By the identity:
$$x_k = \binom{n-1}{\left\lfloor \frac{k-1}{2} \right\rfloor - 1} = \binom{n-2}{\left\lfloor \frac{k-1}{2} \right\rfloor - 1} + \binom{n-2}{\left\lfloor \frac{k-3}{2} \right\rfloor - 1}$$
we get each coefficient twice, matching the sum of $y_i$.

8. Comparing the Sums

For $2 \leq k \leq n+1$, we need:
$$\sum_{j=k+1}^{n+1} x_j \geq \sum_{j=k+1}^{n+1} y_j$$
The right sum is a sum of pairs of binomial coefficients, each appearing at most twice. This sum is less than the maximal possible sum, ensuring:
$$\sum_{j=k+1}^{n+1} y_j \leq \sum_{j=k+1}^{n+1} x_j$$

9. Conclusion

By induction, the largest sum $S$ for $n+1$ numbers is given by:
$$S_{\text{max}} = \sum_{k=2}^{n+1} \binom{n-1}{\left\lfloor \frac{k-1}{2} \right\rfloor - 1} a_k$$
This completes the proof.

$\blacksquare$