Salutations, this is the first time that I see an exercise about mathematical analysis and inequalities, this just for academical curiosity and I would like to understand better this kind of exercises.
This is the case study:
Given m-subsets of an n-element set: $A_1, ..., A_m$
Denote by $|A_i|$ the number of elements of the set $A_i$. Consider the inequality: $$n^2 \sum_{i,j,k=1}^m |A_i \bigcap A_j \bigcap A_k| \geq (|A_1|+...+|A_m|)^3$$
In which the indices $i,j,k$ can be all the values from 1 to $m$, that is, the sum of all $m^3$ terms?.
-Prove this inequality for $m=3$.
-Prove this inequality for an arbitrary positive integer $m$.
So, I require any guidance or starting steps or explanations about how to approach this kind of exercises.
Thanks very much for your attention.
$\bf Lemma$ : $x_1,\dots,x_n\geq 0\implies n^{d-1}\sum_{i=1}^nx_i^d\geq\big(\sum_{i=1}^nx_i\big)^d$
$\bf Proof$ : $\;\;\;$ Note both $n^{d-1}\sum_{i=1}^nx_i^d,\big(\sum_{i=1}^nx_i\big)^d$ remain unchanged after removing those $x_i$ equal to $0$ or any permutation of indices and so we may assume $\mathbf{x}=(x_1,\dots,x_n)$ is an $n$-tuple of non-decreasing positive integers. Let $[n]=\{1,\dots,n\}$ and totally order $[n]^d:=[n]\times\cdots\times[n]$ lexicophically so that it is partitioned together by the half-open intervals of the form $I_a:=[(a,\dots,a),(a+1,\dots,a+1))$ each of size $n^{d-1}$.
Since $(i_1,\dots,i_d)\in I_a\implies x_{a+1}^d\geq\prod_{j=1}^d x_{i_j}$ we must have $n^{d-1}x_{a+1}^d\geq\sum_{(i_1,\dots,i_d)\in I_a}\prod_{j=1}^d x_{i_j}$ and therefore $\sum_{i=1}^nn^{d-1}x_i^d\geq\sum_{a\in[n]}\sum_{(i_1,\dots,i_d)\in I_a}\prod_{j=1}^d x_{i_j}=\big(\sum_{i=1}^nx_i\big)^d$. $\bf QED$
$$ \text{GENERAL}\;\text{CLAIM}\;:\;n^{d-1}\cdot\sum_{(i_1,\dots,i_d)\in[m]^d}\big|\bigcap_{j=1}^d A_{i_j}\big|\geq\big(\sum_{i=1}^m|A_i|\big)^d$$
$\text{PROOF} :$ Both the LHS and RHS above, denoted $\mathcal F(\mathcal A),\Vert\mathcal A\Vert^d$ respectively, remain unchanged after $\mathcal A:=(A_i)_{i=1}^m$ is replaced with $\mathcal A'$ obtained by deleting the empty coordinates in $\mathcal A$ or concatenating the list of distinct singleton subsets of $A_i$ for each $i\in[m]:=\{1,\dots,m\}$. Thus we may assume $\mathcal A=(\{a_i\})_{i=1}^m$ and $[n]=\bigcup_{i=1}^mA_i$. For each $i\in[n]$ let $x_i$ denote the positive number of coordinates in $\mathcal A$ which equal $\{i\}$ so that $\mathcal F(\mathcal A)=n^{d-1}\cdot\sum_{i=1}^nx_i^d\geq\big(\sum_{i=1}^nx_i\big)^d=(\sum_{i=1}^m|A_i|)^d=\Vert\mathcal A\Vert^d.$