For $1\leq k \leq n+1$, consider the set $S\_k$ of functions $f:\{1,\ldots,n\} \rightarrow \{1,\ldots,n+1\}$, with the property that $|f^{-1}\{1,\ldots,k\}| < k$. Note that $|S\_1|=n^n$, and $|S\_{n+1}| = (n+1)^n$. Is it true that $|S\_k|$ grows with $k$? 


It's not hard to come up with the formula
$$ |S\_k| = \sum\_{j=0}^{k-1} {n \choose j} k^j (n+1-k)^{n-j}$$
and if you plot this it is at least apparent that the conjecture should be true.


Another vague observation is that, if you divide by $(n+1)^n$ and take limit as $n\rightarrow \infty$, keeping $k$ fixed, you get the expression
$$ e^{-k} \sum\_{j=0}^{k-1} \frac{k^j}{j!}$$
and using Taylor's integral remainder theorem you can prove the conjecture at least in the limit.



Counting discrete functions
OK, once I went into "preaching", I feel I am obliged to post a solution too.


Let's consider $n$ i.i.d. Bernoulli variables $X\_j$ such that $P(X\_j=1)=\frac k{n+1}$ and $P(X\_j=0)=1-\frac k{n+1}$. We want to show that the probability of the event $\sum\_j X\_j<k$ is increasing in $k$. Note that we can model it as $n$ games where the player has $0$ dollars to start with and plays until he either goes down to $-k$ or reaches $n+1-k$. The problem asks to show that the probability to win less than $k$ games increases as $k$ goes up from $1$ to $n$.


Let us play each game until we reach either $n-k$ or $-k$ and then take a short break to look around. Let $P\_m$ be the probability that at this moment $m$ games out of $n$ are in the position $n-k$. Assume that we are playing up to $-k$ and $n+1-k$. Then if we are at $-k$ already, it is a sure loss. If we are at $n-k$, it is still uncertain. Thus, the probability we are interested in for $k$, is 
$$
\sum\_{m<k}P\_m+\sum\_{m\ge k}P\_m Q(m\to <k)
$$
where $Q(m\to<k)$ is the probability to go from the position with $m$ "almost won" games to that with $<k$ really won games. Similarly, if we are playing up to $-(k+1)$ and $n-k$, the probability in question is 
$$
1-\sum\_{m>k}P\_m-\sum\_{m\le k}P\_m Q(m\to>k)
$$
Thus, the first probability is less than the second iff
$$
P\_k>\sum\_{m\ge k}P\_m Q(m\to <k)+\sum\_{m\le k}P\_m Q(m\to>k)
$$
Note now that $P\_m<P\_k$ for $k\ne m$. Thus, it will suffice to show that
$$
\sum\_{m\ge k}Q(m\to <k)+\sum\_{m\le k}Q(m\to>k)\le 1
$$ 
The probability to get the unexpected outcome of an almost finished game is $\frac{1}{n+1}$. Thus, this sum can be rewritten as 
$$
\sum\_{u=0}^{n-k} P\left(\sum\_{j=1}^{k+u}Y\_j\ge u+1\right)+\sum\_{u=0}^k P\left(\sum\_{j=1}^{n-k+u}Y\_j\ge u+1\right)
$$
where $Y\_j$ are independent Bernoulli with $P(Y\_j=1)=\frac{1}{n+1}$.
Thus, it will suffice to show that
$$
\sigma\_s=\sum\_{u=0}^\infty P\left(\sum\_{j=1}^{s+u}Y\_j\ge u+1\right)\le \frac sn
$$
However, this is an identity. I'll just prove it by induction in $s$. The base $s=0$ is obvious. Now, conditioning upon the length $\ell$ of the initial streak of $1$'s in the sequence $Y\_j$, we have
$$
\sigma\_{s+1}=\sum\_{\ell\ge 0}\left(\frac 1{n+1}\right)^\ell\frac{n}{n+1}(\ell+\sigma\_s)=\frac 1n+\sigma\_s
$$
because when $s\ge 1$, the conditional probability $P\left(\sum\_{j=1}^{s+u}Y\_j\ge u+1\mid Y\_1=\dots=Y\_\ell=1,Y\_{\ell+1}=0\right)$ equals $1$ if $u\le\ell-1$ and $P\left(\sum\_{j=\ell+2}^{s+u}Y\_j\ge (u-\ell)+1\right)=P\left(\sum\_{j=1}^{(s-1)+(u-\ell)}Y\_j\ge (u-\ell)+1\right)$ for $u\ge\ell$.


