How to prove that $\frac{a^ab^b}{a!b!}\le\frac{(a+b)^{(a+b)}}{(a+b)!}$?

Question

As stated in the question. Thank you!

$$\frac{a^ab^b}{a!b!}\le\frac{(a+b)^{(a+b)}}{(a+b)!}$$

Answer 1

HINT: Note that the desired inequality is equivalent to

$$a^ab^b\binom{a+b}a\le(a+b)^{a+b}\;.\tag{1}$$

Suppose that you have $a$ odd numbers and $b$ even numbers. You’re going to draw an ordered sample of $a$ numbers, replacing each number after it’s drawn, so that you could conceivably get the same number every time. You’re also going to draw an ordered sample of $b$ even numbers in the same fashion. You are then going to merge the two samples in any fashion that maintains the relative order of the odd numbers and the relative order of the even numbers.

There are $a^a$ ways to choose the odd numbers, $b^b$ ways to choose the even numbers, and $\binom{a+b}a$ ways to decide which $a$ positions in the merged list will contain odd numbers, so the whole task can be carried out in $a^ab^b\binom{a+b}a$ ways.

Now see if you can find a related interpretation of $(a+b)^{a+b}$ that counts all of these lists and possibly some others as well.

Answer 2

Base case: Assume $a=b=0$. Then $\frac{0^00^0}{0!0!}\le\frac{(0+0)^{(0+0)}}{(0+0)!}$ goes to $1 \le 1$, which is true.

Inductive case: Suppose $a=b$. Increase $b$ to equal $a+k$ for positive $k$. Then $\frac{a^a(a+k)^{a+k}}{a!(a+k)!}\le\frac{(a+a+k)^{(a+a+k)}}{(a+a+k)!}$ rearranges to $\frac{(2a+k)!}{a!(a+k)!} \le \frac{(2a+k)^{2a+k}}{a^a(a+k)^{a+k}}$ at which point you can compare each piece: $(2a+k)! \le (2a+k)^{2a+k}$, $a! \le a^a$, and $(a+k)! \le (a+k)^{a+k}$.

The same can be said for setting $a$ equal to $b+k$.

Answer 3

Just using calculus.

If you use Stirling approximation, that is to say $$n! \sim \sqrt{2\pi n}\left(\frac n e\right)^n$$ the expression $$\frac{a^ab^b}{a!b!}\le\frac{(a+b)^{(a+b)}}{(a+b)!}$$ becomes $$\frac{e^{a+b}}{2 \pi \sqrt{a} \sqrt{b}}\le \frac{e^{a+b}}{\sqrt{2 \pi } \sqrt{a+b}}$$ which becomes $$1 \le \frac{\sqrt{2 \pi } \sqrt{a} \sqrt{b}}{\sqrt{a+b}}=\frac{\sqrt{2 \pi a b} }{\sqrt{a+b}}\implies a+b \leq 2\pi a b$$ which looks simpler to analyze.

Answer 4

It is easy to check that if $a,b$ are two positive real numbers, then $\frac{a^a b^b}{(a+b)^{a+b}}$ is the maximum value of the function $f(x)=x^a(1-x)^b$ over the interval $[0,1]$, attained at $x=\frac{a}{a+b}$. By Euler's beta function we have: $$ \int_{0}^{1}f(x)\,dx = \frac{\Gamma(a+1)\Gamma(b+1)}{\Gamma(a+b+2)}=\frac{1}{a+b+1}\cdot\frac{a! b!}{(a+b)!}\tag{1}$$

Over the interval $\left(0,\frac{a}{a+b}\right)$ the function $(1-x)^b$ is bounded by one, as well as over the interval $\left(\frac{a}{a+b},1\right)$ the function $x^a$ is bounded by one. That leads to: $$ \int_{0}^{1}f(x)\,dx \leq \int_{0}^{\frac{a}{a+b}}x^a\,dx + \int_{\frac{a}{a+b}}^{1}(1-x)^b\,dx \\=\frac{1}{a+1}\left(\frac{a}{a+b}\right)^{a+1}+\frac{1}{b+1}\left(\frac{b}{a+b}\right)^{b+1}\tag{2} $$

On the other hand, over the interval $\left(0,\frac{a}{a+b}\right)$ the function $(1-x)^b$ is lower-bounded by $\left(\frac{b}{a+b}\right)^b$, as well as over the interval $\left(\frac{a}{a+b},1\right)$ the function $x^a$ is lower-bounded by $\left(\frac{a}{a+b}\right)^a$. That leads to:

$$ \int_{0}^{1}f(x)\,dx \geq \frac{1}{a+1}\left(\frac{a}{a+b}\right)^{a+1}\left(\frac{b}{a+b}\right)^b+\frac{1}{b+1}\left(\frac{b}{a+b}\right)^{b+1}\left(\frac{a}{a+b}\right)^a\tag{3}$$ that is equivalent to:

$$ \int_{0}^{1}f(x)\,dx \geq \frac{a^a b^b}{(a+b)^{a+b}}\left(\frac{\frac{a}{a+1}+\frac{b}{b+1}}{a+b}\right)\tag{4}$$ so: $$ \frac{a!b!}{(a+b)!}\geq \frac{a^a b^b}{(a+b)^{a+b}}\left(\frac{\frac{a}{a+1}+\frac{b}{b+1}}{a+b}\right)(a+b+1)\tag{5} $$ and:

$$ \frac{a^a b^b}{a! b!}\leq \frac{(a+b)^{a+b}}{(a+b)!}\cdot\frac{a+b}{(a+b+1)\left(\frac{a}{a+1}+\frac{b}{b+1}\right)}\tag{6} $$

is a stronger inequality than the one we wanted to prove, since $(a+b+1)\left(\frac{a}{a+1}+\frac{b}{b+1}\right)\geq (a+b)$.