Inequality with increasing variables

Question

If $n,k\ge2$, and $0\le a_0\le a_1\le\cdots$, prove that \[\left(\frac{1}{k n} \sum_{l=0}^{k n-1} a_{l}\right)^{k} \geq \frac{1}{n} \sum_{i=0}^{n-1} \prod_{j=0}^{k-1} a_{n j+i}.\]

This inequality is an improvement of AM-GM inequality. For $n=3, k=2$, $0\le a_0\le a_1\le\cdots\le a_5$, the inequality is \[\left(\frac{a_0+a_1+\cdots+a_5}{6}\right)^2\geq \frac{a_0a_3+a_1a_4+a_2a_5}{3}.\]

This is a homogeneous inequality, so WLOG, let $\displaystyle\sum_{l=0}^{kn-1}a_l=kn$. We have to prove \[\sum_{i=0}^{n-1} \prod_{j=0}^{k-1} a_{n j+i}\le n.\label1\tag1\]

I tried to use Carlson inequality, it became \[\left(\sum_{i=0}^{n-1} \prod_{j=0}^{k-1} a_{n j+i}\right)^n\le\prod_{i=0}^{k-1}\sum_{j=0}^{n-1}a_{ni+j}^n\overset?\le n^n.\] However this doesn't make use of the condition $0\le a_0\le a_1\le\cdots$.

From another perspective we could use the adjustment method. I can prove that $\forall~0\le t\le k-1$, the numbers $a_{tn}$, $a_{tn+1}$ $\ldots$ $a_{(t+1)n-1}$ can take at most three different values to reach maximum.

Answer 1

(With the homogenization of $\sum a_i = kn$.)

First, we consider the $ k = 2, n = 2$ case.
Suppose $ a + b + c + d = 4, a \leq b \leq c \leq d$, we want to show that $ ac + bd \leq 2$.

Intuitvely, if $a \leq d$ are fixed, we'd want to increase $b$ and decrease $c$ subject to $ b \leq c $.
Hence, we replace $(a, b, c, d)$ with $ ( a , \frac{b+c}{2}, \frac{b+c}{2}, d)$, which only increases the value.
This becomes $ a \times \frac{b+c}{2} + \frac{b+c}{2} \times d = (a+d)(b+c) / 2$, which by AM-GM, we know it has a maximum value of $2$, hence we are done.

Equality occurs when $ a + d = b+c = 2$ and $ b = c ( = 1)$. EG $(0, 1, 1, 2)$ and $(1, 1, 1, 1)$ are equality cases.

Note: The hint about the equality condition is that it encourages you to realize that $a+d = b+c = 2$, and so we'd want to force that out somehow.Otherwise, one might think of $(a+b)(c+d)$ instead, but that doesn't help us classify the equality cases, nor have I had success exploring that path.

---

Now we consider the $k = 3, n = 2$ case.
Suppose $ a + b + c + d + e + f = 6, a\leq b \leq c \leq d \leq e \leq f$, we want to show that $ ace + bdf \leq 2$.
If $a, d, e, f$ are fixed, then since $a \leq d, e\leq f$ so $ae \leq df$ and we'd want to increase $b$ and decrease $c$ subject to $ b \leq c$.
Similarly, if $a, b, c, f$ are fixed, since $ac \leq bf$, we'd want to increase $d$ and decrease $e$ subject to $ d \leq e$.
Thus, we replace $(a, b, c, d, e, f)$ with $(a, \frac{b+c}{2}, \frac{b+c}{2},\frac{d+e}{2}, \frac{d+e}{2},f )$, which only increase the value. Again, the expression becomes $(a+f)(b+c)(d+e) / 4$, which by AM-GM has a maximum value of 2, and we are done.

Equality holds when $ a +f = b + c = d+e = 2, b = c ( = 1), d = e (= 1)$.

---

Now we consider the $k = 2, n = 3 $ case.
Suppose $ a +b + c + d + e + f = 6 , a\leq b \leq c \leq d \leq e \leq f,$ we want to show that $ ad + be + cf \leq 3$.
If $ a \leq f$ are fixed, we'd want to decrease d, increase c subject to $ c \leq d$.
Thus we replace $(a, b, c, d, e, f)$ with $(a, b, \frac{c+d}{2}, \frac{c+d}{2}, e, f)$.

• If $ b+e \geq c+d$, then we'd want to replace $(b, e)$ with $(\frac{c+d}{2}, b+e - \frac{c+d}{2})$. Then, we're maximizing $(c+d)/2 \times (6 - 3*(c+d)/2) $, which has a maximum of $3$ wen $ (c+d)/2 = 1$.
• Otherwise, if $b+e < c+d$, then we'd want to replace $(b, e) $ with $( b+e - \frac{c+d}{2}, \frac{c+d}{2} )$. Then, we're likewise maximizing $(c+d)/2 \times (6 - 3*(c+d)/2)$, which has a maximum of $3$ when $(c+d)/2 = 1$.

The equality cases are

• $(a, b, 1, 1, 1, f)$ subject to $ a \leq b \leq 1 \leq f$, $a+b+f = 3$.
• $(a, 1, 1, 1, e, f)$ subject to $ a \leq 1 \leq e \leq f$, $a+e+f = 3$.

---

I leave you to generalize this, in the exact same way as shown above.
Maybe think about the $ k = 3, n = 3$ case, how can we use the above ideas?
Once you've done that, please post a general solution.

Answer 2

The idea of a proof

Calvin Lin's answer investigates how we can tweak $\sum_{i=0}^{n-1} \prod_{j=0}^{k-1} a_{n j+i}$ to make it bigger.

Here is a way to tweak that sum of products so that it is amenable to induction. To illustrate the idea, let us set $k=3$ and $n=4$. Suppose we have an increasing sequence of nonnegative numbers shown on the left. $$\begin{matrix}&a_0, &a_1, &a_2, &a_3\\ &a_4, &a_5, &a_6, &\color{red}{a_7}\\ &a_8, &a_9, &a_{10}, &a_{11}\end{matrix} \quad\Longrightarrow\begin{array}{cccl}&a_0, &a_1, &a_2, &a_3\\ &a_4, &a_5, &a_6, &\color{red}{a_7}\\ &\color{blue}{a_7}, &\color{blue}{a_7}, &\color{blue}{a_7}, &a_{11}+\color{blue}{a_8+a_9+a_{10}-3a_7}\end{array}$$
We would like to increase $a_0a_4a_8+a_1a_5a_9+a_2a_6a_{10}+a_3a_7a_{11}$ without changing $\sum_i a_i$.

Since $a_0a_4$ is at most $a_3a_7$, we can shrink $a_8$ to $a_7$ and increase $a_{11}$ by $a_8-a_7$ so that the sum $a_0a_4a_8+a_3a_7a_{11}$ may get bigger. Ditto for $a_1a_5$ and $a_2a_6$. The new sum of products that corresponds to the new increasing sequence of numbers as shown on the right, $a_0a_4\color{red}{a_7}+a_1a_5\color{red}{a_7}+a_2a_6\color{red}{a_7}+a_3\color{red}{a_7}(a_{11}+a_8+a_9+a_{10}-3a_7)$ is $\color{red}{a_7}(a_0a_4+a_1a_5a+a_2a_6+a_3a_8')$, where $a_8'=a_{11}+a_8+a_9+a_{10}-3a_7$. What is nice here is: $a_0a_4+a_1a_5a+a_2a_6+a_3a_8'$ is the sum of products for the case $k=2$ and $n=4$ with the increasing numbers $a_0, \cdots, a_7, a_8'$.

A proof

Let us do induction on $k$ for the inequality where $k,n\ge1$.

If $k=1$, the inequality is trivial.

Suppose it is true for $k\ge1$ as induction hypothesis. Consider the case with $k+1$. Assume $n\ge2$; otherwise $n=1$ is trivial. Suppose we have $0\le a_0\le a_1\le\cdots\le a_{(k+1)n-1}$. We want to prove $$n\left(\frac{1}{(k+1) n} \sum_{l=0}^{(k+1) n-1} a_{l}\right)^{k+1} \ge\sum_{i=0}^{n-1} \prod_{j=0}^{k} a_{n j+i}.$$

Since for all $i$, $0\le i\le n-2$, \begin{aligned}\prod_{j=0}^{k} a_{n j+i}&=(a_{nk-1}+(a_{nk+i}-a_{nk-1}))\prod_{j=0}^{k-1} a_{n j+i}\\ &\le a_{nk-1}\prod_{j=0}^{k-1} a_{n j+i} + (a_{nk+i}-a_{nk-1})\prod_{j=0}^{k-1} a_{n j+n-1}\end{aligned} we have the first inequality in the computation below. \begin{aligned} &\quad\quad\sum_{i=0}^{n-1} \prod_{j=0}^{k} a_{n j+i}\\ &\le\sum_{i=0}^{n-2}\left(a_{nk-1}\prod_{j=0}^{k-1} a_{n j+i} + (a_{nk+i}-a_{nk-1})\prod_{j=0}^{k-1} a_{n j+n-1}\right) + \prod_{j=0}^{k} a_{n j+(n-1)}\\ &=a_{nk-1}\sum_{i=0}^{n-2}\prod_{j=0}^{k-1} a_{n j+i}+\left(\sum_{i=0}^{n-2}a_{nk+i}-(n-1)a_{nk-1}+a_{n(k+1)-1}\right)\prod_{j=0}^{k-1} a_{n j+n-1}\\ &=a_{nk-1}\left(\sum_{i=0}^{n-2}\prod_{j=0}^{k-1} a_{n j+i}+\left(\sum_{i=0}^{n-2}a_{nk+i}-(n-1)a_{nk-1}+a_{n(k+1)-1}\right)\prod_{j=0}^{k-2} a_{n j+n-1}\right)\\ &\le a_{nk-1}n\left(\frac{1}{k n} (\sum_{l=0}^{kn-2}a_l +a_{kn-1}')\right)^k \\ &=\frac n{(kn)^kkn} (kna_{nk-1})\left(\sum_{l=0}^{kn-2}a_l +a_{kn-1}'\right)^k \\ &\le\frac n{(kn)^kkn} \left(\frac{kna_{nk-1}+k\left(\sum_{l=0}^{kn-2}a_l +a_{kn-1}'\right)}{k+1}\right)^{k+1} \\ &=\frac n{(kn)^kkn} \left(\frac{k\sum_{l=0}^{(k+1) n-1} a_{l}}{k+1}\right)^{k+1} \\ &=n\left(\frac{1}{(k+1) n} \sum_{l=0}^{(k+1) n-1} a_{l}\right)^{k+1}\\ \end{aligned}

where $a_{kn-1}'=\sum_{i=0}^{n-1}a_{nk+i}-(n-1)a_{nk-1}+a_{n(k+1)-1}$, which is $\ge a_{n(k+1)-1}$.
Note that $0\le a_0\le a_1\le\cdots\le a_{kn-3}\le a_{kn-2}\le a'_{kn-1}$, we can apply the induction hypothesis, obtaining the second inequality in the computation above. The last inequality in the computation above is the AM-GM inequality.

Induction is complete.

Answer 3

Just an idea to simplify the problem :

Take your example :

$$\frac{(a_0+a_1+a_2+a_3+a_4+a_5)^2}{36}\geq \frac{a_0a_3+a_1a_4+a_2a_5}{3}$$

Now if we have :

$$\frac{(a_0+a_1+a_2+a_3+a_4+a_5)^2}{3}\geq \left(a_{2}+a_{5}\right)^{2}+\left(a_{1}+a_{4}\right)^{2}+k\left(a_{0}+a_{3}\right)^{2}$$

Or :

$$\frac{(x+y+z)^2}{3}\geq x^2+y^2+kz^2$$

Or :

$$\frac{(u+v+1)^2}{3}\geq u^2+v^2+k$$

Or :

$$\frac{(u+v+1)^2}{3}-u^2-v^2\geq k$$

On the other hand we need to show :

$$\left(a_{2}+a_{5}\right)^{2}+\left(a_{1}+a_{4}\right)^{2}+k\left(a_{0}+a_{3}\right)^{2}\geq 4(a_0a_3+a_1a_4+a_2a_5)$$

Or :

$$k\left(a_{0}+a_{3}\right)^{2}\ge 4a_0a_3$$

Or :

$$k\geq 1-c^2$$

Remains to show :

$$\frac{(u+v+1)^2}{3}-u^2-v^2\geq 1-c^2$$

Wich is simpler and true if and $\left(u-1\right)^{2}+\left(v-1\right)^{2}\leq 1-c^{2},c\in[0,1]$

Some details :

$$x=a_2+a_5,y=a_1+a_4,z=a_0+a_3,u=\frac{a_{2}+a_{5}}{a_{0}+a_{3}},v=\frac{a_{1}+a_{4}}{a_{0}+a_{3}},c=\frac{a_3-a_0}{a_0+a_3}$$

PS: We don't need to expand.