Prove the function is nondecreasing Lets take: $A_1,...,A_n$ family of finite, nonempty sets. Define: $$f(t)=\sum_{k=1}^n\left( \sum_{1\le i_1<...<i_k\le n}(-1)^{k-1}t^{|A_{i_1} \cup ... \cup A_{i_k}|} \right)$$ for $t \in [0,1]$. Prove that $f$ is nondecreasing.
That is the problem from IMC (problem number 4: solutions), the presented solution uses probability theory and I would like to see more direct proof, yet I am not able to do that. I've tried to use induction (failed to succes) and computed the derivative which is $0$ at $0$ and $1$ but nothing elese came from that. Do you have any sugesstions how to approache that problem without probability arguments?
 A: I can get rid of the explicit appeal to probability by showing combinatorially that $f\upharpoonright\big(\Bbb Q\cap(0,1]\big)$ is monotone non-decreasing and then extending the result to $f\upharpoonright[0,1]$ by continuity. Note, though, that at bottom it’s really the same basic argument.
Let $c$ be an integer greater than $1$, and let $g\le c$ be a positive integer. Let $A=\bigcup_{k=1}^nA_k$, and let $m=|A|$. For $k=1,\ldots,n$ let
$$\mathscr{A}_k(g,c)=\left\{f\in{^A[c]}:f[A_k]\subseteq[g]\right\}\;.$$
Suppose that $1\le i_1<i_2<\ldots<i_k\le n$ and $f\in{^A[c]}$; then $f\in\bigcap_{j=1}^k\mathscr{A}_{i_j}(g,c)$ if and only if $f\left[\bigcup_{j=1}^kA_{i_j}\right]\subseteq[g]$. Thus, 
$$\left|\bigcap_{j=1}^k\mathscr{A}_{i_j}(g,c)\right|=g^{\left|\bigcup_{j=1}^kA_{i_j}\right|}c^{m-\left|\bigcup_{j=1}^kA_{i_j}\right|}=c^m\left(\frac{g}c\right)^{\left|\bigcup_{j=1}^kA_{i_j}\right|}\;.$$
The inclusion-exclusion principle, whose use is suggested by the form of $f$, then says that
$$\begin{align*}
\left|\bigcup_{k=1}^n\mathscr{A}_k(g,c)\right|&=\sum_{k=1}^n\,\sum_{1\le i_1<i_2<\ldots<i_k\le n}(-1)^{k-1}\left|\bigcap_{j=1}^k\mathscr{A}_{i_j}(g,c)\right|\\\\
&=c^m\sum_{k=1}^n\,\sum_{1\le i_1<i_2<\ldots<i_k\le n}(-1)^{k-1}\left(\frac{g}c\right)^{\left|\bigcup_{j=1}^kA_{i_j}\right|}\\\\
&=c^mf\left(\frac{g}c\right)
\end{align*}$$
and hence that
$$c^{-m}\left|\bigcup_{k=1}^n\mathscr{A}_k(g,c)\right|=f\left(\frac{g}c\right)\;.$$
Thus, $f\left(\frac{g}c\right)$ is the fraction of functions from $A$ to $[c]$ that are in $\bigcup_{k=1}^n\mathscr{A}_k(g,c)$.
Let $q_0,q_1\in\Bbb Q\cap(0,1]$ with $q_0\le q_1$. Then there are $g_0,g_1,c\in\Bbb Z^+$ such that $q_i=\frac{g_i}c$ for $i=0,1$. Clearly $g_0\le g_1$, so $\bigcup_{k=1}^n\mathscr{A}_k(g_0,c)\subseteq\bigcup_{k=1}^n\mathscr{A}_k(g_1,c)$, and therefore $f\left(\frac{g_0}c\right)\le f\left(\frac{g_1}c\right)$. Thus, $f\upharpoonright\big(\Bbb Q\cap(0,1]\big)$ is monotone non-decreasing.
Finally observe that $f(t)$ is a polynomial in $t$ and therefore continuous, so $f$ must be monotone non-decreasing on $[0,1]$.
