How to prove that $cov(f(X_1, X_2, \ldots ,X_n), g(X_1, X_2, \ldots ,X_n)) \geq 0$ for $X_1, \ldots, X_n$ independent and $f,g$ increasing? I read in a talk that a consequence of the FKG inequality is that:
$$
cov(f(X_1, X_2, \ldots ,X_n), g(X_1, X_2, \ldots ,X_n)) \geq 0
$$ 
for $X_1, X_2, \ldots ,X_n$ independent and $f,g$ increasing in each coordinate, that is, in example, $f(X_1, X_2, \ldots ,X_n)$ is increasing in $X_1$ for fixed $X_2, \ldots, X_n$. 
However, I read in a paper that this can be proved using a bounding theorem, ie., Chernoff, Chebychev, etc. Does anyone have any idea how to do this It states that one can prove the two variable case and then use induction, but I am failing how to see this is proven in even the two variable case. Thanks!
 A: Warning: we solve this problem, for the case where 
$X_1,\cdots, X_n\in\{0,1\}.$
Let $X=f(X_1,\cdots, X_n)$ and $Y=g(X_1,\cdots, X_n)$, for $X_1,\cdots, X_n$ independents and $f,g$ increasing. 
We follow a variant (of the idea) of the book: Additive Combinatorics of Terence Tao and Van Vu.
By induction on n,
if $n=1$, the result is trivial. In this case, it is sufficient to note that 
$
(f(x_1)-f(x_2))(g(x_1)-g(x_2))\geqslant 0$, for all $x_1,x_2\in\{0,1\}
$
and then integrate over $\{0,1\}\times\{0,1\}$. Assume that the result is valid for n=k-1.  By definition,
\begin{align}
\mathbb{E}(X|X_k)
=
\sum_{i_k\in\{0,1\}}\mathbb{E}\left(f(X_1,\cdots,X_{K-1},i_k)|C^{i_k}_k\right)\mathbb{1}_{\{X_k=i_k\}}
=
\sum_{i_k\in\{0,1\}}\mathbb{E}\left(f(X_1,\cdots,X_{K-1},i_k)\right)\mathbb{1}_{\{X_k=i_k\}}, \quad (1)
\end{align}
where $C^{i_k}_k=\{\pmb{x}=(x_1,\cdots,x_n): x_{k}=i_{k}\}$ is the cylinder of basis $\{i_{k}\}$. The second equality above is valid for independence. Using (1), note that the application 
$\pmb{x}\mapsto \mathbb{E}(X|X_k)(\pmb{x})$ is increasing. In fact,
if $\pmb{x}\preceq\pmb{y}$ (if and only if $x_i\leqslant y_i$, $i=1,\cdots ,n$), we have
$$
\mathbb{E}(X|X_k)(\pmb{x})
=
\sum_{i_k\in\{0,1\}}\mathbb{E}\left(f(X_1,\cdots,X_{K-1},i_k)\right)\mathbb{1}_{\{X_k=i_k\}}(\pmb{x})
\leqslant
\sum_{i_k\in\{0,1\}}\mathbb{E}\left(f(X_1,\cdots,X_{K-1},i_k)\right)\mathbb{1}_{\{X_k=i_k\}}(\pmb{y})
\\
\hspace{4,5cm}=
\mathbb{E}(X|X_k)(\pmb{y}),
$$
where we use that $f$ is increasing function.
Then 
$
\mathbb{E}(X|X_k)(\pmb{1})
\geqslant 
\mathbb{E}(X|X_k)(\pmb{0})
$ 
and
$
\mathbb{E}(Y|X_k)(\pmb{1})
\geqslant 
\mathbb{E}(Y|X_k)(\pmb{0})
$, implying
$$
\hspace{-6cm}
\mathbb{E}(X|X_k)(\pmb{1}) \, \mathbb{E}(Y|X_k)(\pmb{0})
+
\mathbb{E}(X|X_k)(\pmb{0}) \, \mathbb{E}(Y|X_k)(\pmb{1})
\\
\hspace{6cm}\leqslant
\mathbb{E}(X|X_k)(\pmb{1}) \, \mathbb{E}(Y|X_k)(\pmb{1})
+
\mathbb{E}(X|X_k)(\pmb{0}) \, \mathbb{E}(Y|X_k)(\pmb{0}).
\quad (2)
$$
By inductive hypothesis, for $\pmb{b}=(b,\cdots,b)$, $b=0,1,$ we have
$$
\hspace{-6cm} \mathbb{E}(XY|X_k)(\pmb{b})
=
\mathbb{E}\left(f(X_1,\cdots,X_{k-1},b)\, g(X_1,\cdots,X_{k-1},b)\right)
\\ 
\hspace{6cm}\geqslant 
\mathbb{E}\left(f(X_1,\cdots,X_{k-1},b)\right)\, \mathbb{E}\left(g(X_1,\cdots,X_{k-1},b)\right)
\\
\hspace{10cm}=
\mathbb{E}(X|X_k)(\pmb{b}) \, 
\mathbb{E}(Y|X_k)(\pmb{b}). \quad (3)
$$
By other hand,
$$
\hspace{-6cm}
\mathbb{E}(XY)=\mathbb{E}(XY|X_k)(\pmb{0})\, \mathbb{P}(X_k=0)+ \mathbb{E}(XY|X_k)(\pmb{1})\, \mathbb{P}(X_k=1)
\\
\hspace{1,8cm}
\stackrel{(3)}{\geqslant}
\mathbb{E}(X|X_k)(\pmb{0})\, \mathbb{E}(Y|X_k)(\pmb{0})\,\mathbb{P}(X_k=0)
+
\mathbb{E}(X|X_k)(\pmb{1})\, \mathbb{E}(Y|X_k)(\pmb{1})\,\mathbb{P}(X_k=1).
\quad (4)
$$
Finally, we have that
$$
\hspace{-6cm}
\mathbb{E}(X)\mathbb{E}(Y)
=
\left[
\mathbb{E}(X|X_k)(\pmb{0})\,\mathbb{P}(X_k=0)
+
\mathbb{E}(X|X_k)(\pmb{1})\,\mathbb{P}(X_k=1)
\right]
\\
\hspace{6cm}
\times
\left[
\mathbb{E}(Y|X_k)(\pmb{0})\,\mathbb{P}(X_k=0)
+
\mathbb{E}(Y|X_k)(\pmb{1})\,\mathbb{P}(X_k=1)
\right]
\\ \hspace{-2cm}
\stackrel{(2)}{\leqslant}
\left[\mathbb{E}(X|X_k)(\pmb{0})\, \mathbb{E}(Y|X_k)(\pmb{0})\right]
\left[\mathbb{P}^2(X_k=0)+\mathbb{P}(X_k=0)\mathbb{P}(X_k=1)\right]
\hspace{5,5cm}+
\left[\mathbb{E}(X|X_k)(\pmb{1})\, \mathbb{E}(Y|X_k)(\pmb{1})\right]
\left[\mathbb{P}^2(X_k=1)+\mathbb{P}(X_k=0)\mathbb{P}(X_k=1)\right]
=
\left[\mathbb{E}(X|X_k)(\pmb{0})\, \mathbb{E}(Y|X_k)(\pmb{0})\right]
\mathbb{P}(X_k=0)
+
\left[\mathbb{E}(X|X_k)(\pmb{1})\, \mathbb{E}(Y|X_k)(\pmb{1})\right]
\mathbb{P}(X_k=1)
\\
\stackrel{(4)}{\leqslant}
\mathbb{E}(XY).
$$
