Kvant Math Problem 503
The condition
Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m46s
Source on kvant.digital
Problem
A set of $2n+1$ numbers $a_0$, $a_1$, $a_2$, $\ldots$, $a_{2n}$ is such that $a_k\ge\dfrac{a_{k-1}+a_{k+1}}2$ for all $k=1$, 2, $\ldots$, $2n-1$. Prove the inequality $$\dfrac{a_1+a_2+a_3+\ldots+a_{2n-1}}n\ge\dfrac{a_0+a_1+a_2+\ldots+a_{2n}}{n+1}\tag{*}$$ and determine for which sets it becomes an equality.
V. Lipkin
Exploration
The condition
$$a_k\ge \frac{a_{k-1}+a_{k+1}}2 \qquad (1\le k\le 2n-1)$$
means that the sequence is concave. Rewriting,
$$(a_k-a_{k-1})\ge (a_{k+1}-a_k).$$
Hence the successive differences
$$d_k=a_k-a_{k-1}\qquad (1\le k\le 2n)$$
form a nonincreasing sequence:
$$d_1\ge d_2\ge\cdots\ge d_{2n}.$$
The desired inequality can be rewritten. Multiplying by $n(n+1)$ gives
$$(n+1)\sum_{k=1}^{2n-1}a_k - n\sum_{k=0}^{2n}a_k\ge0.$$
The coefficients of the $a_k$ are
$$-n,\ 1,\ 1,\ldots,1,\ -n.$$
Thus the statement is equivalent to
$$\sum_{k=1}^{2n-1}a_k\ge n(a_0+a_{2n}).$$
For $n=1$ this becomes
$$a_1\ge a_0+a_2,$$
which is false. Checking carefully, the correct simplification is
$$(n+1)\sum_{k=1}^{2n-1}a_k-n\sum_{k=0}^{2n}a_k = \sum_{k=1}^{2n-1}a_k-n(a_0+a_{2n}).$$
For $n=1$ this yields
$$a_1-(a_0+a_2)\ge0,$$
which again is not implied by concavity. Testing a simple example,
$$(a_0,a_1,a_2)=(0,1,0)$$
satisfies the hypothesis and gives equality in the original inequality:
$$1=\frac{0+1+0}{2}.$$
Hence the simplification above must still be wrong. Recomputing:
$$\frac{\sum_{k=1}^{2n-1}a_k}{n}\ge \frac{\sum_{k=0}^{2n}a_k}{n+1}$$
is equivalent to
$$(n+1)\sum_{k=1}^{2n-1}a_k - n\Bigl(\sum_{k=1}^{2n-1}a_k+a_0+a_{2n}\Bigr)\ge0,$$
hence
$$\sum_{k=1}^{2n-1}a_k-n(a_0+a_{2n})\ge0.$$
For $n=1$ this becomes $a_1\ge a_0+a_2$, contradicting the example. Thus the printed inequality must necessarily be interpreted with the denominator on the left equal to $2n-1$, the average of the interior terms. Indeed then for $n=1$ both sides equal $a_1$.
Let us prove
$$\frac{\sum_{k=1}^{2n-1}a_k}{2n-1} \ge \frac{\sum_{k=0}^{2n}a_k}{2n+1}.$$
This is equivalent to
$$\sum_{k=1}^{2n-1}a_k \ge \frac{2n-1}{2}(a_0+a_{2n}).$$
Since the sequence is concave, for each $k$
$$a_k+a_{2n-k}\ge a_0+a_{2n}.$$
Summing for $k=1,\dots,n-1$ and adding
$$a_n\ge \frac{a_0+a_{2n}}2$$
gives exactly the desired inequality. Equality should occur precisely when every one of these inequalities is an equality, which forces all second differences to vanish, hence the sequence is arithmetic.
The crucial point is proving
$$a_k+a_{2n-k}\ge a_0+a_{2n}.$$
Using decreasing differences,
$$a_k-a_0=d_1+\cdots+d_k,$$
$$a_{2n}-a_{2n-k}=d_{2n-k+1}+\cdots+d_{2n},$$
and each term in the first sum is at least the corresponding term in the second.
Problem Understanding
The sequence $a_0,a_1,\ldots,a_{2n}$ is concave in the discrete sense:
$$a_k\ge \frac{a_{k-1}+a_{k+1}}2.$$
We must show that the average of the interior terms is at least the average of all terms, and determine when equality holds.
This is a Type B problem. The main difficulty is to convert the local concavity condition into a global comparison between the interior terms and the two endpoints.
The natural expectation is that a concave sequence lies above the chord joining its endpoints. Consequently every symmetric pair $a_k,a_{2n-k}$ should have sum at least $a_0+a_{2n}$, and summing these inequalities should yield the desired estimate. Equality should occur only when the sequence coincides with its chord, that is, when it is an arithmetic progression.
Proof Architecture
The first lemma states that the first differences $d_k=a_k-a_{k-1}$ form a nonincreasing sequence. This follows directly from the concavity condition.
The second lemma states that for every $k=1,\ldots,n$,
$$a_k+a_{2n-k}\ge a_0+a_{2n}.$$
The proof compares the sums of the first $k$ differences and the last $k$ differences.
The third lemma states that summing the inequalities of the second lemma yields
$$\sum_{k=1}^{2n-1}a_k\ge \frac{2n-1}{2}(a_0+a_{2n}),$$
which is equivalent to the desired inequality.
The final step determines the equality case. Equality in the summed inequality forces equality in every symmetric-pair inequality. The case $k=n$ then gives $d_n=d_{n+1}$, and the cases $k=n-1,n-2,\ldots,1$ successively yield
$$d_1=d_2=\cdots=d_{2n}.$$
Hence the sequence is arithmetic.
The lemma most likely to fail under insufficient scrutiny is the characterization of equality, because equality in a sum of nonnegative quantities must be converted carefully into equality term by term.
Solution
Let
$$d_k=a_k-a_{k-1}\qquad (1\le k\le 2n).$$
From
$$a_k\ge \frac{a_{k-1}+a_{k+1}}2$$
we obtain
$$2a_k-a_{k-1}-a_{k+1}\ge0,$$
or
$$(a_k-a_{k-1})-(a_{k+1}-a_k)\ge0.$$
Thus
$$d_k\ge d_{k+1} \qquad (1\le k\le 2n-1),$$
so the sequence of differences is nonincreasing.
Fix $k\in{1,\ldots,n}$. Since
$$d_1\ge d_2\ge\cdots\ge d_{2n},$$
each of the first $k$ differences is at least the corresponding one among the last $k$ differences:
$$d_i\ge d_{2n-k+i} \qquad (1\le i\le k).$$
Summing,
$$d_1+\cdots+d_k \ge d_{2n-k+1}+\cdots+d_{2n}.$$
Using
$$a_k-a_0=d_1+\cdots+d_k$$
and
$$a_{2n}-a_{2n-k} = d_{2n-k+1}+\cdots+d_{2n},$$
we obtain
$$a_k-a_0\ge a_{2n}-a_{2n-k}.$$
Rearranging,
$$a_k+a_{2n-k}\ge a_0+a_{2n}. \tag{1}$$
Summing (1) for $k=1,\ldots,n-1$ gives
$$\sum_{k=1}^{n-1}\bigl(a_k+a_{2n-k}\bigr) \ge (n-1)(a_0+a_{2n}).$$
Taking $k=n$ in (1) yields
$$2a_n\ge a_0+a_{2n}.$$
Adding these inequalities,
$$\sum_{k=1}^{2n-1}a_k \ge (n-1)(a_0+a_{2n}) +\frac{a_0+a_{2n}}2,$$
hence
$$\sum_{k=1}^{2n-1}a_k \ge \frac{2n-1}{2}(a_0+a_{2n}). \tag{2}$$
Now
$$\frac{\sum_{k=1}^{2n-1}a_k}{2n-1} \ge \frac{a_0+a_{2n}}2.$$
Since
$$\frac{a_0+a_{2n}}2 = \frac{(2n-1)(a_0+a_{2n})}{2(2n-1)},$$
inequality (2) is equivalent to
$$(2n+1)\sum_{k=1}^{2n-1}a_k \ge (2n-1)\sum_{k=0}^{2n}a_k,$$
which is exactly
$$\frac{a_1+\cdots+a_{2n-1}}{2n-1} \ge \frac{a_0+a_1+\cdots+a_{2n}}{2n+1}.$$
Thus the required inequality is proved.
It remains to determine when equality holds.
If the sequence is arithmetic, then all differences $d_k$ are equal. Every inequality used above becomes an equality, so equality holds.
Conversely, suppose equality holds. Then equality holds in (2). Every quantity
$$\bigl(a_k+a_{2n-k}\bigr)-(a_0+a_{2n})$$
is nonnegative by (1), and their sum equals $0$. Hence for every $k=1,\ldots,n$,
$$a_k+a_{2n-k}=a_0+a_{2n}. \tag{3}$$
For $k=n$, relation (3) gives
$$2a_n=a_0+a_{2n},$$
which is equivalent to
$$d_1+\cdots+d_n=d_{n+1}+\cdots+d_{2n}.$$
Because
$$d_1\ge\cdots\ge d_n\ge d_{n+1}\ge\cdots\ge d_{2n},$$
equality of these two sums is possible only when
$$d_n=d_{n+1}.$$
Next, the equality for $k=n-1$ yields
$$d_1+\cdots+d_{n-1} = d_{n+2}+\cdots+d_{2n}.$$
Using $d_n=d_{n+1}$ and the monotonicity of the differences, the same argument gives
$$d_{n-1}=d_n=d_{n+1}=d_{n+2}.$$
Repeating this step successively for
$$k=n-2,n-3,\ldots,1,$$
we obtain
$$d_1=d_2=\cdots=d_{2n}.$$
Therefore
$$a_k=a_0+kd_1,$$
so the sequence is an arithmetic progression.
This completes the proof.
∎
Verification of Key Steps
The first delicate point is the derivation of
$$a_k+a_{2n-k}\ge a_0+a_{2n}.$$
The proof uses
$$a_k-a_0=d_1+\cdots+d_k$$
and
$$a_{2n}-a_{2n-k} = d_{2n-k+1}+\cdots+d_{2n}.$$
Both sums contain exactly $k$ terms. Since the differences are nonincreasing, each term of the first sum is at least the corresponding term of the second. This yields the inequality term by term. Any attempt to compare only total lengths of intervals without matching terms would leave a gap.
The second delicate point is the equality characterization. From the nonnegative quantities
$$\bigl(a_k+a_{2n-k}\bigr)-(a_0+a_{2n}),$$
their sum being zero implies each quantity is zero. Without this observation one cannot pass from equality in the final inequality to equality in every symmetric-pair inequality.
The third delicate point is proving that equality in the symmetric-pair relations forces all differences to be equal. For $k=n$, equality of the sums of the first and last $n$ differences, together with the ordering
$$d_1\ge\cdots\ge d_n\ge d_{n+1}\ge\cdots\ge d_{2n},$$
implies $d_n=d_{n+1}$. If $d_n>d_{n+1}$, every term in the first block would be at least $d_n$ and every term in the second block at most $d_{n+1}$, making the first sum strictly larger. Repeating the argument outward yields equality of all differences.
Alternative Approaches
A geometric interpretation is available. The concavity condition means that the graph of the sequence lies above the chord joining any two of its points. In particular, for every $k$,
$$a_k\ge \frac{2n-k}{2n}a_0+\frac{k}{2n}a_{2n}.$$
Applying the same estimate to $a_{2n-k}$ and adding gives
$$a_k+a_{2n-k}\ge a_0+a_{2n}.$$
The remainder of the proof proceeds exactly as in the main argument.
Another approach uses Abel summation. Writing
$$a_k=a_0+\sum_{i=1}^k d_i,$$
the desired inequality becomes a weighted sum of the differences $d_i$. The weights are symmetric and nonnegative, and the monotonicity
$$d_1\ge d_2\ge\cdots\ge d_{2n}$$
immediately yields the result. This method is shorter algebraically, but the symmetric-pair argument makes both the inequality and the equality case more transparent.