# 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.

-
oh I have edit. – math110 Mar 29 '13 at 11:17
It never hurts to post your solution, if you already have one. It may inspire others to find other proofs, or we may be able to help you make it a cleaner solution. – TMM Mar 29 '13 at 14:25
Perhaps some counting argument will work: number of ways of colouring n spots with n colours is $n^n$. – Aryabhata Mar 29 '13 at 15:42
A simple convexity argument gets you to within a factor of two without any computation. – cardinal Mar 29 '13 at 16:43
@cardinal : would you care to elaborate ? I believe this “convexity argument” is only an optical illusion. – Ewan Delanoy Mar 29 '13 at 17:01

## 4 Answers

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, if we use \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\\ &=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}$$

-
Impressed. (+1) – Ron Gordon Mar 30 '13 at 17:38
Now, "just" prove that the sequence is monotone in $n$ for $n \geq 3$, which I believe it is. (+1) :-) – cardinal Mar 30 '13 at 18:05
By the way, strictly speaking, from what you've shown, I think is should be $\limsup$ in the first display and not $\lim$. – cardinal Mar 30 '13 at 18:23
@cardinal: Yes, technically, you are correct. However, the estimate $(2)$ is more accurate as $n$ gets larger and so, with a bit more care, and perhaps a lot more writing, this would show that the limit is $\frac12$. – robjohn Mar 30 '13 at 19:14
Oh, Thank you robjohn, It's good job. – math110 Mar 31 '13 at 8:39

One can use Abel's identity: How to prove $\sum_{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.$$

-
$(-1)^k(-1)^{n-k-1}=(-1)^{n-1}$. I do not see any problem with mine. – i707107 Nov 10 '13 at 16:46
Ah, I missed that $(k-n)^k$ in the second equation was changed to $(n-k)^k$ in the third. Sorry about that. Good proof (+1). By not explicitly giving limits on the sum, you somewhat bypassed the difficulty at $k=0$ and $k=n$. – robjohn Nov 10 '13 at 17:30
$0$-th power should be considered as $1$ for convention. But, $k=0$ and $k=n$ do not appear from my second expression anyway. – i707107 Nov 10 '13 at 20:39
I always take $0^0=1$, but the problem in Abel's formula is that it goes from $k=0$ to $k=n$ and we divide by $k$ and $n-k$. I felt the need to mention that for $n\ge2$, those terms can be disregarded because they are zero. In my answer, I needed to deal with that since I included the limits of summation. That's all. – robjohn Nov 10 '13 at 22:05

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.$

-
How can we prove your first claim? Could you please write it for me? – user64066 Apr 1 '13 at 9:11
@user64066 : Let me make sure I understand which claim you are referring to. The inequality in the first paragraph is proved in the body of the post. Is there a specific paragraph that you would like me to elaborate on? – Will Orrick Apr 1 '13 at 9:23
@user64066 : There is an error in the argument. It is possible for a translate of a balanced sequence to be balanced. For example, 1133 and 2244 are both 2-balanced. I'll have to think about whether any part of the counting argument can be salvaged. – Will Orrick Apr 1 '13 at 11:23

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.

-