Proving that $\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\frac{1}{2}n^n$

How can we prove that $$\displaystyle\sum_{i=0}^{n}\binom{n}{i}i^{n-i}(n-i)^{i}\le\dfrac{1}{2}n^n$$ where $\displaystyle\binom{n}{i}=\dfrac{n!}{i!(n-i)!}$.

This inequality is very interesting. I think this problem has nice methods, but my method is very ugly.

Since the full result has not yet been shown, I post this.

Here is a proof that $$ \limsup_{n\to\infty}\frac1{n^n}\sum_{k=0}^n\binom{n}{k}k^{n-k}(n-k)^k\le\frac12\tag{1} $$ Using the bound $$ \binom{n}{k}\le\frac1{\sqrt{2\pi}}\frac{n^{n+1/2}}{k^{k+1/2}(n-k)^{n-k+1/2}}\tag{2} $$ we get $$ \begin{align} &\frac1{n^n}\sum_{k=0}^n\binom{n}{k}k^{n-k}(n-k)^k\\ &\le\frac1{\sqrt{2\pi}}\sum_{k=0}^n\sqrt{\frac{n\vphantom{k}}{k(n-k)}}\left(\frac{k}{n-k}\right)^{n-2k}\\ &=\frac1{\sqrt{2\pi}}\sum_{k=-n/2}^{n/2}\sqrt{\frac{4n^2}{n^2-4k^2}}\left(\frac{n+2k}{n-2k}\right)^{-2k}\frac1{\sqrt{n}}\tag{$k\mapsto k+n/2$}\\ &=\frac1{\sqrt{2\pi}}\sum_{k=-n/2}^{n/2}\frac2{\sqrt{1-4k^2/n^2}}\left(\frac{1+2k/n}{1-2k/n}\right)^{-2k}\frac1{\sqrt{n}}\tag{3} \end{align} $$ The sum on the right hand side of $(3)$ is a Riemann Sum ($x=k/\sqrt{n}$) for $$ \frac1{\sqrt{2\pi}}\int_{-\infty}^\infty 2\,e^{-8x^2}\,\mathrm{d}x=\frac12\tag{4} $$

Towards a full solution

Since we are using $x=k/\sqrt{n}$, we have that $(3)$ approximates $$ \frac1{\sqrt{2\pi}}\int_{-\sqrt{n}/2}^{\sqrt{n}/2}\frac2{\sqrt{1-4x^2/n}}\left(\frac{1+2x/\sqrt{n}}{1-2x/\sqrt{n}}\right)^{-2x\sqrt{n}}\,\mathrm{d}x\tag{5} $$ As $n$ increases to $\infty$, $\displaystyle\frac2{\sqrt{1-4x^2/n}}$ increases to $2$ and $\displaystyle\left(\frac{1+2x/\sqrt{n}}{1-2x/\sqrt{n}}\right)^{-2x\sqrt{n}}$ increases to $e^{-8x^2}$. Thus, it is not unreasonable to infer that $(3)$ increases to $\frac12$,

Abel's Identity

As i707107 mentions, Abel's identity is very useful here. In fact, $$ \begin{align} &\sum_{k=0}^n\binom{n}{k}(a+tk)^{k-1}(b-tk)^{n-k}\\ &=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n}{k}(a+tk)^{k-1}\binom{n-k}{j}(-1)^{n-k-j}(a+b)^j(a+tk)^{n-k-j}\\ &=\sum_{k=0}^n\sum_{j=0}^{n-k}\binom{n}{n-k}\binom{n-k}{j}(a+tk)^{n-j-1}(-1)^{n-k-j}(a+b)^j\\ &=\sum_{j=0}^n\sum_{k=0}^{n-j}\binom{n}{j}\binom{n-j}{k}(a+tk)^{n-j-1}(-1)^{n-k-j}(a+b)^j\\[6pt] &=a^{-1}(a+b)^n\tag{6} \end{align} $$ where the last equality is because for $j\lt n$, the sum in $k$ is an $n-j$ repeated difference of an $n-j-1$ degree polynomial in $k$, hence $0$, and for $j=n$, the sum in $k$ is a single term.

Set $a=n$, $b=0$, and $t=-1$ in $(6)$ to get $$ \sum_{k=0}^n\binom{n}{k}(n-k)^{k-1}k^{n-k}=n^{n-1}\tag{7} $$ The inequality is true for $n=1$, i.e. $0\le\frac12$, but false for $n=0$. Let's assume that $n\ge2$ so that we can leave out the $k=0$ and $k=n$ terms of Abel's identity since they are $0$.

Then $$ \begin{align} &\sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\\ &=\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}(n-k)k^{n-k}\\ &=n\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}k^{n-k} -\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac{k}{n-k}\\ &=n\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^{k-1}k^{n-k} -\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac{n-k}{k}\\ &=n^n-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\frac12\left(\frac{k}{n-k}+\frac{n-k}{k}\right)\\ &\le n^n-\sum_{k=1}^{n-1}\binom{n}{k}(n-k)^kk^{n-k}\\ &=n^n-\sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\tag{8} \end{align} $$ The last inequality is because $\frac12\left(x+\frac1x\right)\ge1$ for $x\gt0$.

Adding the left side of $(8)$ to both sides and dividing by $2$ yields $$ \sum_{k=0}^n\binom{n}{k}(n-k)^kk^{n-k}\le\frac12n^n\tag{9} $$

One can use Abel's identity: How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$?

Abel's identity is: $$\sum_k\binom{n}{k}(k+s-n)^{k}(r+n-k)^{n-k-1}=\frac{(r+s)^n}{r}$$

We use this with $s=0$ and $r=-n$, we have $$\sum_k\binom{n}{k}(k-n)^k(-k)^{n-k-1}=\frac{(-n)^n}{-n}$$

It follows that

$$\sum_k\binom{n}{k}(n-k)^kk^{n-k}\frac{n}{k}=n^n$$ Substitution $k$->$n-k$ gives $$\sum_k\binom{n}{k}(n-k)^kk^{n-k}\frac{n}{n-k}=n^n$$ On the other hand, $\frac{n}{k}+\frac{n}{n-k}=\frac{n^2}{(n-k)k}\geq 4$ for $1\leq k\leq n-1$. Hence $$4\sum_k\binom{n}{k}(n-k)^kk^{n-k}\leq \sum_k\binom{n}{k}(n-k)^kk^{n-k}\left(\frac{n}{k}+\frac{n}{n-k}\right)=2n^n.$$

I was hoping that by interpreting the left-hand side as an enumeration problem, there would be a relatively simple combinatorial proof. So far this hasn't panned out. I had thought it possible to obtain a strong partial result, but this turned out to be mistaken. (See below.) Perhaps someone can figure out how to turn these ideas into something that acually works.

The left-hand side of the OP's inequality can be interpreted as the enumeration of what I have called "balanced sequences". If anyone knows the proper name for these, please let me know. Let $\Sigma$ equal $\{1,2,\ldots,n\}^n,$ that is, the set of sequences of length $n$ of numbers from the set $\{1,2,\ldots,n\}.$ For $r\in\mathbf{Z}$ we say that $\sigma\in\Sigma$ is $r$-balanced if the number of elements greater than $r$ in $\sigma$ equals $r.$ You can see that there are no $0$-balanced or $n$-balanced sequences. Some examples: if $n=4,$ then the sequences $2111,$ $1211,$ $1114$ are $1$-balanced; the sequences $2234,$ $4321,$ $4411$ are $2$-balanced; the sequences $1444$ and $4443$ are $3$-balanced. Define a sequence to be balanced if it is $r$-balanced for some $r,$ and unbalanced otherwise.

In general, the number of $r$-balanced sequences is $$\binom{n}{r}r^{n-r}(n-r)^r$$ since there are $\binom{n}{r}$ ways to choose the positions for the low elements in the sequence, $r^{n-r}$ ways of assigning low elements to those positions, and $(n-r)^r$ ways of assigning high elements to the remaining positions. (Here "low" means less than or equal to $r;$ "high" means greater than $r.)$

Observe that if $\sigma$ is both $r$-balanced and $s$-balanced, then $r=s$. For if $s<r,$ then $\sigma$ has $r$ elements greater than $r,$ which means that it has at least $r$ elements greater than $s.$ This contradicts that $\sigma$ has exactly $s$ elements greater than $s.$ Since a balanced sequence is therefore $r$-balanced for exactly one $r,$ the number of balanced sequences is $$\sum_{r=0}^n\binom{n}{r}r^{n-r}(n-r)^r,$$ which must therefore be less than or equal to $\lvert\Sigma\rvert=n^n.$

To obtain the factor $1/2$ on the right, it would suffice to find an injective map from the set of balanced sequences to the set of unbalanced sequences. Unfortunately, I have been unable to devise such a map. robjohn's result shows that this may be delicate: as $n$ approaches infinity, $\Sigma$ will be roughly evenly split between balanced and unbalanced sequences.

Some incorrect material here: I had thought there was a simple argument leading to the inequality $$\sum_{r=0}^n\binom{n}{r}r^{n-r}(n-r)^r\le n^n-(n-1)^n=[1-(1-1/n)^n]n^n.$$ For large $n,$ the right-hand side is approximately $(1-1/e)n^n\approx 0.632n^n.$ Unfortunately, the argument was flawed. I quote it here for future reference.

One gets a partial result as follows. Let $\Sigma_-=\{1,2,\ldots,n-1\}^n.$ Define the right translates of $\sigma\in\Sigma_-$ to be the sequences in $\Sigma$ of the form $\sigma+c,$ where $c\ge1$ and $\sigma+c$ is the sequence obtained from $\sigma$ by adding $c$ to every one of its elements. Clearly we must have $c\le c_\max=n-\max(\sigma).$

It is not hard to see that right translates of a balanced sequence are unbalanced. It then follows that $\Sigma$ contains at least $(n-1)^n$ unbalanced sequences. For every sequence $\sigma\in\Sigma_-$ is either unbalanced, or has a right translate $\sigma+c_\max$ in $\Sigma\setminus\Sigma_-$ that is unbalanced. (The map that takes a balanced sequence in $\Sigma_-$ to its maximal right translate in $\Sigma\setminus\Sigma_-$ is invertible - merely translate leftward until the sequence becomes balanced.) This proves that there are at most $n^n-(n-1)^n$ balanced sequences.

The flaw is that right translates of balanced sequences are not necessarily unbalanced. A simple example is $1133$ and its right translate $2244,$ both of which are $2$-balanced. I guess I was misled by the examination of many $r$-balanced sequences $\sigma\in\Sigma_-$ with the property that $r$ was an element of $\sigma.$ In this case, one can prove that $\sigma+1$ is unbalanced as follows. Let $\rho_j(\sigma)$ be the number of elements of $\sigma$ that are greater than $j.$ If the table of values $\rho_l(\sigma)$ looks like $$\begin{array}{c|cccccccccc} j & 0 & 1 & 2 & \ldots & r-1 & r & r+1 & \ldots & n-1 & n\\ \hline\rho_j(\sigma) & n & a_1 & a_2 & \ldots & a_{r-1} & r & a_{r+1} & \ldots & 0 & 0 \end{array},$$ then the corresponding table for $\rho_j(\sigma+1)$ looks like $$\begin{array}{c|ccccccccccc} j & 0 & 1 & 2 & \ldots & r-1 & r & r+1 & \ldots & n-1 & n\\ \hline\rho_j(\sigma+1) & n & n & a_1 & \ldots & a_{r-2} & a_{r-1} & r & \ldots & a_{n-2} & 0 \end{array}.$$ The sequence $a_1,a_2,\ldots,a_{n-2}$ is nonincreasing, and, since $r$ is an element of $\sigma,$ we have $a_{r-1}>r$. Therefore $\sigma+1$ is unbalanced. This argument does not work if $r$ is not an element of $\sigma$ since then $a_{r-1}=r.$ It also fails for $\sigma+c$ with $c>1.$

This was Question 10 from the 2009 Sydney University Mathematics Society (SUMS) problem solving competition, see here. A combinatorial solution interpreting the problem in terms of trees can be found in the last section of the solutions here.