Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
oh I have edit. –  math110 Mar 29 '13 at 11:17
1  
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
2  
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
1  
A simple convexity argument gets you to within a factor of two without any computation. –  cardinal Mar 29 '13 at 16:43
1  
@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 4

up vote 7 down vote accepted

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

share|improve this answer
    
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.$$

share|improve this answer
    
$(-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.$

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.