For positive integer $n\geq 3$ and real numbers $a_1,...,a_n,b_1,...,b_n$, prove the following. $$\sum_{i=1}^n a_i(b_i-b_{i+3})\leq\frac{3n}{8}\sum_{i=1}^n((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$$($a_{n+1}=a_1$, and for $i=1,2,3$ $b_{n+i}=b_i$.)
Problem
Source: 2023 KMO Final Round Day 2 Problem 6
Tags: algebra, inequalities
26.03.2023 10:34
Claim) $\Sigma (a_i -a_{i+k})^2 \le k^2 \Sigma (a_i -a_{i+1})^2$
Note that the inequality doesnt change by adding the constant $c$ to all $ a_i (1\le i \le n)$. Therefore, we can assume that $\Sigma a_i =0$. Now, firstly divide by 3 in each side. Using AM-GM on the left side, $LHS \le \frac{2}{n} \Sigma a_i ^2 +\frac{n}{8} \Sigma (\frac{b_i -b_{i+3}}{3})^2$ By Claim), $\Sigma (\frac{b_i -b_{i+3}}{3})^2 \le \Sigma (b_i -b_{i+1})^2$ Therefore, all we need to prove is the following. $\Sigma a_i ^2 \le \frac{n^2}{16} \Sigma (a_i -a_{i+1})^2$ It is okay to deduct $\frac{1}{n} (\Sigma a_i )^2$ on the left side, since it's 0. Then multiple by $2n$ in each side. Then it transforms to the following. $\Sigma (a_i -a_{i+1})^2 + \Sigma (a_i -a_{i+2})^2 +\cdots +\Sigma (a_i -a_{i+n-1})^2 \le \frac{n^3}{8} \Sigma (a_i -a_{i+1})^2$ Using Claim), $LHS \le \Sigma (a_i -a_{i+1})^2 \cdot (1^2 +2^2 +\cdots +2^2 +1^2)$ When n is odd, $1^2 +2^2 +\cdots +2^2 +1^2 =2\frac{\frac{n-1}{2}\frac{n+1}{2}n}{6} =\frac{n^3 -n }{12}\le \frac{n^3}{8}$ When n is even, $1^2 +2^2 +\cdots +2^2 +1^2 =2\frac{\frac{n-2}{2}\frac{n}{2}(n-1)}{6} +\frac{n^2}{4}=\frac{n^3 + n^2 }{12} \le \frac{n^3}{8}$
26.03.2023 12:24
qwedsazxc wrote: For positive integer $n\geq 3$ and real numbers $a_1,...,a_n,b_1,...,b_n$, prove the following. $$\sum_{i=1}^n a_i(b_i-b_{i+3})\geq\frac{3n}{8}\sum_{i=1}^n((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$$($a_{n+1}=a_1$, and for $i=1,2,3$ $b_{n+i}=b_i$.) I think the $\ge$ in the inequality should be $\le$…
27.03.2023 10:43
Acorn-SJ wrote: qwedsazxc wrote: For positive integer $n\geq 3$ and real numbers $a_1,...,a_n,b_1,...,b_n$, prove the following. $$\sum_{i=1}^n a_i(b_i-b_{i+3})\geq\frac{3n}{8}\sum_{i=1}^n((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$$($a_{n+1}=a_1$, and for $i=1,2,3$ $b_{n+i}=b_i$.) I think the $\ge$ in the inequality should be $\le$… Fixed it. Thanks for pointing out.
27.03.2023 14:04
chrono223 wrote: Claim) $\Sigma (a_i -a_{i+k})^2 \le k^2 \Sigma (a_i -a_{i+1})^2$
Note that the inequality doesnt change by adding the constant $c$ to all $ a_i (1\le i \le n)$. Therefore, we can assume that $\Sigma a_i =0$. Now, firstly divide by 3 in each side. Using AM-GM on the left side, $LHS \le \frac{2}{n} \Sigma a_i ^2 +\frac{n}{8} \Sigma (\frac{b_i -b_{i+3}}{3})^2$ By Claim), $\Sigma (\frac{b_i -b_{i+3}}{3})^2 \le \Sigma (b_i -b_{i+1})^2$ Therefore, all we need to prove is the following. $\Sigma a_i ^2 \le \frac{n^2}{16} \Sigma (a_i -a_{i+1})^2$ It is okay to deduct $\frac{1}{n} (\Sigma a_i )^2$ on the left side, since it's 0. Then multiple by $2n$ in each side. Then it transforms to the following. $\Sigma (a_i -a_{i+1})^2 + \Sigma (a_i -a_{i+2})^2 +\cdots +\Sigma (a_i -a_{i+n-1})^2 \le \frac{n^3}{8} \Sigma (a_i -a_{i+1})^2$ Using Claim), $LHS \le \Sigma (a_i -a_{i+1})^2 \cdot (1^2 +2^2 +\cdots +2^2 +1^2)$ When n is odd, $1^2 +2^2 +\cdots +2^2 +1^2 =2\frac{\frac{n-1}{2}\frac{n+1}{2}n}{6} =\frac{n^3 -n }{12}\le \frac{n^3}{8}$ When n is even, $1^2 +2^2 +\cdots +2^2 +1^2 =2\frac{\frac{n-2}{2}\frac{n}{2}(n-1)}{6} +\frac{n^2}{4}=\frac{n^3 + n^2 }{12} \le \frac{n^3}{8}$ I dont know how to prove the claim) inequality can you write it down please, i think i dont get the sigma sign well
30.03.2023 06:06
shinhue wrote:
I don't know how to prove the Claim) inequality. Can you write it down please? I think I don't get the ∑ sign well. A detailed solution can be found here.
21.05.2023 11:05
Since $\frac{3n}{8}$ is definitely not the best bound, we’ll try to find a better bound $\lambda_n<\frac{3n}{8}$ Some preparations: Lemma $1$: (Ky Fan) If $\sum_{i=1}^{n}a_i=0$, then $cos\frac{2\pi}{n}\cdot\sum_{i=1}^{n} a_i^2\ge\sum_{i=1}^{n}a_ia_{i+1}$ It’s a well-known inequality that can be proved by Fourier transform, we will not post the details. Lemma $2$: When $n\ge 3$, $sin \frac{\pi}{n}\ge\frac{3\sqrt3}{2n}$ Proof: Let $f(n)=nsin\frac{\pi}{n}-\frac{3\sqrt3}{2}$ Note that $tan\frac{\pi}{n}\ge\frac{\pi}{n}$, Then $f’(n)=cos\frac{\pi}{n}\cdot(tan\frac{\pi}{n}-\frac{\pi}{n})\ge 0\Longrightarrow f$ increases $\Longrightarrow f(n)\ge f(3)=0$ The lemma is proved. Back to the original problem Step $1$: Note that for every $\epsilon\in\mathbb{R}$, we have $\sum_{i=1}^{n}(a_i-\epsilon)(b_i-a_{i+3})=\sum_{i=1}^{n}a_i(b_i-b_{i+3})-\epsilon\sum_{i=1}^{n}(b_i-b_{i+3})=\sum_{i=1}^{n}a_i(b_i-b_{i+3})$ So we may assume $\sum_{i=1}^{n}a_i=0$ Step $2$: $\sum_{i=1}^{n}(b_i-b_{i+1})^2=\frac{1}{3}\cdot\sum_{i=1}^{n}((b_i-b_{i+1})^2+(b_{i+1}-b_{i+2})^2+(b_{i+2}-b_{i+3})^2\underset{Cauchy}{\ge}\frac{1}{9}\sum_{i=1}^{n}(b_i-b_{i+3})^2$ Step $3$: $\sum_{i=1}^{n}a_i(b_i-b_{i+3})\underset{AM-GM}{\leq} \alpha_n\cdot\sum_{i=1}^{n}a_i^2+\frac{1}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+3})^2$ Where $\alpha_n>0$ and will be determined later. Step $4$: With Step $1$ and Lemma $1$, we have $\frac{\sum_{i=1}^{n}(a_i-a_{i+1})^2}{\sum_{i=1}^{n}a_i^2}=2-2\cdot\frac{\sum_{i=1}^{n}a_ia_{i+1}}{\sum_{i=1}^{n}a_i^2}\ge 2-2cos\frac{2\pi}{n}=4sin^2\frac{\pi}{n}$ In Conclusion, $\sum_{i=1}^{n}a_i(b_i-b_{i+3})^2\underset{Step 3}{\leq}\alpha_n\cdot\sum_{i=1}^{n}a_i^2+\frac{1}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+3})^2$ $\underset{Step2,4}{\leq}\frac{\alpha_n}{4sin^2\frac{\pi}{n}}\cdot\sum_{i=1}^{n}(a_i-a_{i+1})^2+\frac{9}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+1})^2$ Let $\frac{\alpha_n}{4sin^2\frac{\pi}{n}}=\lambda=\frac{9}{4\alpha_n}$ Then $\alpha_n=3sin\frac{\pi}{n},\lambda_n=\frac{3}{4sin\frac{\pi}{n}}$ obviously satisfy the original problem. So $\sum_{i=1}^{n}a_i(b_i-b_{i+3})\leq\frac{3}{4sin\frac{\pi}{n}}\cdot\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$ $\underset{Lemma1}{\leq}\frac{3}{4\cdot\frac{3\sqrt3}{2n}}\cdot\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)<\frac{3n}{8}\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$ We’re done.
28.09.2023 13:29
hrqdcj wrote: Since $\frac{3n}{8}$ is definitely not the best bound, we’ll try to find a better bound $\lambda_n<\frac{3n}{8}$ Some preparations: Lemma $1$: (Ky Fan) If $\sum_{i=1}^{n}a_i=0$, then $cos\frac{2\pi}{n}\cdot\sum_{i=1}^{n} a_i^2\ge\sum_{i=1}^{n}a_ia_{i+1}$ It’s a well-known inequality that can be proved by Fourier transform, we will not post the details. Lemma $2$: When $n\ge 3$, $sin \frac{\pi}{n}\ge\frac{3\sqrt3}{2n}$ Proof: Let $f(n)=nsin\frac{\pi}{n}-\frac{3\sqrt3}{2}$ Note that $tan\frac{\pi}{n}\ge\frac{\pi}{n}$, Then $f’(n)=cos\frac{\pi}{n}\cdot(tan\frac{\pi}{n}-\frac{\pi}{n})\ge 0\Longrightarrow f$ increases $\Longrightarrow f(n)\ge f(3)=0$ The lemma is proved. Back to the original problem Step $1$: Note that for every $\epsilon\in\mathbb{R}$, we have $\sum_{i=1}^{n}(a_i-\epsilon)(b_i-a_{i+3})=\sum_{i=1}^{n}a_i(b_i-b_{i+3})-\epsilon\sum_{i=1}^{n}(b_i-b_{i+3})=\sum_{i=1}^{n}a_i(b_i-b_{i+3})$ So we may assume $\sum_{i=1}^{n}a_i=0$ Step $2$: $\sum_{i=1}^{n}(b_i-b_{i+1})^2=\frac{1}{3}\cdot\sum_{i=1}^{n}((b_i-b_{i+1})^2+(b_{i+1}-b_{i+2})^2+(b_{i+2}-b_{i+3})^2\underset{Cauchy}{\ge}\frac{1}{9}\sum_{i=1}^{n}(b_i-b_{i+3})^2$ Step $3$: $\sum_{i=1}^{n}a_i(b_i-b_{i+3})\underset{AM-GM}{\leq} \alpha_n\cdot\sum_{i=1}^{n}a_i^2+\frac{1}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+3})^2$ Where $\alpha_n>0$ and will be determined later. Step $4$: With Step $1$ and Lemma $1$, we have $\frac{\sum_{i=1}^{n}(a_i-a_{i+1})^2}{\sum_{i=1}^{n}a_i^2}=2-2\cdot\frac{\sum_{i=1}^{n}a_ia_{i+1}}{\sum_{i=1}^{n}a_i^2}\ge 2-2cos\frac{2\pi}{n}=4sin^2\frac{\pi}{n}$ In Conclusion, $\sum_{i=1}^{n}a_i(b_i-b_{i+3})^2\underset{Step 3}{\leq}\alpha_n\cdot\sum_{i=1}^{n}a_i^2+\frac{1}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+3})^2$ $\underset{Step2,4}{\leq}\frac{\alpha_n}{4sin^2\frac{\pi}{n}}\cdot\sum_{i=1}^{n}(a_i-a_{i+1})^2+\frac{9}{4\alpha_n}\cdot\sum_{i=1}^{n}(b_i-b_{i+1})^2$ Let $\frac{\alpha_n}{4sin^2\frac{\pi}{n}}=\lambda=\frac{9}{4\alpha_n}$ Then $\alpha_n=3sin\frac{\pi}{n},\lambda_n=\frac{3}{4sin\frac{\pi}{n}}$ obviously satisfy the original problem. So $\sum_{i=1}^{n}a_i(b_i-b_{i+3})\leq\frac{3}{4sin\frac{\pi}{n}}\cdot\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$ $\underset{Lemma1}{\leq}\frac{3}{4\cdot\frac{3\sqrt3}{2n}}\cdot\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)<\frac{3n}{8}\sum_{i=1}^{n}((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)$ We’re done. Nice one!
29.09.2023 06:07
VeryGood wrote:
Nice one! Generalization: This article.
01.10.2023 12:52
Thanks for introducing my work, Rhapsodies_pro.
16.03.2024 18:23
Orc-Lee-Chem wrote: Thanks for introducing my work, Rhapsodies_pro. I really appreciate your nice work, incredible! BUT for the best bound, it can be proved by DFT really easily. For introduction, see my blog. Define $\omega :=e^{\frac{2\pi i}n}$. Consider function $f,g:[n]\to\mathbb R,$ $k\stackrel{f}{\longmapsto}a_k,$ $k\stackrel{g}{\longmapsto}b_k$ for all $k\in [n].$ We have \begin{align*}\sum_{i=1}^n a_i(b_i-b_{i+3})&=\langle f,g\rangle-\langle f,\tau_3g\rangle=\langle\widehat{f},\widehat{g}\rangle-\langle\widehat{f},\widehat{\tau_3g}\rangle=\sum_p(1-\omega^{3p})f(p)\overline{g(p)}\\&\le\sum_p |1-\omega^{3p}|\cdot |f(p)|\cdot |g(p)|\le\sum_p \frac{|1-\omega^{3p}|}2\left(|f(p)|^2+|g(p)|^2\right).\end{align*}\begin{align*}\sum_{i=1}^n((a_i-a_{i+1})^2+(b_i-b_{i+1})^2)&=2(\langle f,f\rangle-\langle f,\tau_1f\rangle)+\langle g,g\rangle-\langle g,\tau_1g\rangle)\\&=2\left(\langle\widehat{f},\widehat{f}\rangle-\langle\widehat{f},\widehat{\tau_1f}\rangle+\langle\widehat{g},\widehat{g}\rangle-\langle\widehat{g},\widehat{\tau_1g}\rangle\right)\\&=\sum_p2\left(1-\cos\frac{2p\pi}n\right)\left(|f(p)|^2+|g(p)|^2\right).\end{align*}We only need $|1-\omega^{3p}|\le \frac{3-4\sin^2\frac {\pi}n}{\sin\frac {\pi}n}\left(1-\cos\frac{2p\pi}n\right),$ which can be easily proved.$\Box$