Submodular functions A few definitions:
A Submodular function $ f:2^E \rightarrow R $ is a function that satisfies the following two equivalent definitions:


*

*for every $ S,T\subseteq E: f(S) + f(T) \geq f(S\cup T)+f(S\cap T) $

*for every $ S,T\subseteq E $ with $ S\subseteq T $ and for every $ x\in E\setminus T : f(S\cup \{x\})-f(S)\geq f(T\cup\{x\}) - f(T) $


A monotone submodular function is a submodular functions such that for every $ S,T \subseteq E $ with $ S\subseteq T : f(T)\geq f(S)  $ . We also define $ f(\emptyset) = 0 $.
Show that  $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) $ where $ e_i\in S $ for all i, where f is a monotone submodular function.
 A: The formula $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) $ is certainly false.If $f$ is a (monotone) submodular function, then $f+c$ with $c \in \mathbb R$ is also a (monotone) submodular function. So you would have $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) + c$ for arbitrary $c \in \mathbb R$, which is obviously not true.
However, it's easy to prove $ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq f(S) - f(\emptyset) $. Simply note that $f(S)-f(S-\{e_i\}) \leq f(S-U)-f(S-U-\{e_i\})$ for $e_i\notin U$. So the sum is bounded by a telescope sum: $$ \sum_{i=1}^n(f(S)-f(S-\{e_i\})\leq \\
(f(S)-f(S-\{e_1\}))+(f(S-\{e_1\}))-f(S-\{e_1, e_2\})+\ldots+(f(S-\cup_{i=1}^{n-1} \{e_i\})-f(S-\cup_{i=1}^n \{e_i\}))\\
=f(S)-f(S-\cup_{i=1}^n \{e_i\}) \leq f(S) - f(\emptyset)$$
Only the last step of replacing $f(S-\cup_{i=1}^n \{e_i\})$ by $f(\emptyset)$ requires monotony.
A: Fix a set $E$ with monotone submodular function $f$. Note that $\tilde{f}(I) := f(I) + \lambda$ also will be a monotone submodular function, for any $\lambda \in \mathbb{R}$, since loosely speaking the same number of $\tilde{f}$'s appear on each side of all inequalities. 
With that for $n = 1$ our desired inequality just reads $f(S - e_1) \geqslant 0$, but by our analysis this can be taken to be arbitrary, in particular negative. 
So perhaps you want some further hypothesis?
