Combinatorial proof of a simple inequality: $\left(\frac{n+1}{2}\right)^n \ge n!$

Question

I want to prove the following inequality combinatorialy $$\left(\frac{n+1}{2}\right)^n \ge n! ,n \in \mathbb{N} $$
my attempts in this direction so far have been $$\left(\frac{n+1}{2}\right)^n \ge n! \iff (n+1)^n \ge 2^n n!$$ then i tried to show a injection from some set with $2^nn!$ elements to a set with $(n+1)^n$ elements but this is where i am not able to come up with a setup that shows this clearly.

I would greatly appreciate any kind of help pointing to such a setup with the injective mapping.

Thank you

Answer 1

Note that $$2^nn!=2\cdot4\cdot\ldots\cdot2n.$$ For $n=2k$, this can be reordered as $$2^nn!=(2\cdot 2n)\cdot(4\cdot2(n-1))\cdot\ldots\cdot(2k\cdot2(k+1)).$$ These are $k$ terms, all of the form $2a\cdot 2b$ with $a+b=n+1$. We find that it suffices to show that $2a\cdot2b\leq(a+b)^2$ for any integers $a,b\geq1$.

A similar argument shows that the case $n=2k+1$ can also be reduced to $2a\cdot2b\leq(a+b)^2$. We just need to get rid of the central factor of $2(k+1)=n+1$.

Now first note that $2a\cdot2b\leq(a+b)^2$ can be easily proved algebraically, since $$(a+b)^2-4ab=(b-a)^2\geq0.$$ We can also prove this geometrically with the following picture, assuming $a\leq b$.

The total area is $(a+b)^2$, so writing it as a sum of its parts, we get $$(a+b)^2=3ab+a^2+a(b-a)+(b-a)^2=4ab+(b-a)^2\geq4ab.$$

But now we can turn the geometric proof into a combinatorial one with an injection. For $[n]=\{1,\ldots,n\}$, consider $f:[4]\times[a]\times[b]\to[a+b]^2$, defined by \begin{equation*} f(i,x,y):=\begin{cases} (x,y+a)&i=1 \\(x+a,y+a)&i=2 \\(y+a,x)&i=3 \\(x,y)&i=4,y\leq a \\(y+a,x+a)&i=4,y>a \end{cases}. \end{equation*} So cases $i=1$ and $i=2$ correspond to the vertical rectangles, case $i=3$ to the horizontal rectangle, case $i=4,y\leq a$ to the $a\times a$ square, and case $i=4,y>a$ to the $(b-a)\times a$ rectangle.

Answer 2

Do we allow a proof that uses combinations and other stuff? If so, here is a proof that uses combinations and induction.

In the expansion of $(1+a)^n$, the coefficient of $a^r$ is the number of ways of choosing $r$ factors from $n$ factors, i.e. $\binom{n}{r}$. So $(1+a)^n=\binom{n}{0}+\binom{n}{1}a+\binom{n}{2}a^2+...+\binom{n}{n}a^n$.

$n!\le\left(\frac{n+1}{2}\right)^n$ is true when $n=1$. Assume $k!\le\left(\frac{k+1}{2}\right)^k$. Then,

$(k+1)!\le(k+1)\left(\frac{k+1}{2}\right)^k=\left(\frac{k+2}{2}\right)^{k+1}\frac{2}{\left(1+\frac{1}{k+1}\right)^{k+1}}=\left(\frac{k+2}{2}\right)^{k+1}\frac{2}{1+1+...}\le\left(\frac{(k+1)+1}{2}\right)^{k+1}$

$\therefore n!\le\left(\frac{n+1}{2}\right)^n$ is true for $n \in \mathbb{N}$.

Answer 3

Here is an explicit bijection.

Sort the strings $x=(x_1,\ldots,x_n)$ in lexicographic order and let $\ell(x)$ be the index of the string $x$ in this list, where $0\leq \ell(x) \leq 2^n-1.$ Sort the permutations $\sigma=(\sigma(1),\ldots,\sigma(n))$ in lexicographic order and let $v(\sigma)$ be the index of permutation $\sigma$ where $0\leq v(\sigma)\leq n!-1.$

Now define the map $f(x,\sigma):=\ell(x)+2^n v(\sigma)$ and note that the map is one to one as well as satisfying $$\#\{f(x,\sigma):x \in \{0,1\}^n,\sigma \in S_n\}=2^n n!,$$ thus this sets up a combinatorial bijection. The reason is that it uses the two functions $\ell(x)$ and $v(\sigma)$ as "components" in a rectangle of sides $2^n \times n!.$

Now encode in base $(n+1)$ the values taken on by the map $f(x,\sigma)$ as $x$ and $\sigma$ vary over their domains. All that's now required is to show that there are enough points to do this encoding which is equivalent to showing that $(n+1)^n \geq 2^n n!$ which can be shown by induction as in one of the other answers.

Answer 4

The inequality is (equivalent to) an instance of the arithmetic-geometric mean (AM-GM) inequality. When applied to the list $[1,2,\ldots,n]$ it states that $\frac{1+2+\cdots+n}n\geq\sqrt[n]{1\times2\times\cdots\times n}$ (with strict inequality for $n>1$) and since the left hand side is $\frac{n+1}2$, it just remains to take $n$-th powers of the (positive) numbers on both sides. Although it is unlikely that one can find a combinatorial argument for the AM-GM inequality in general (which involves arbitrary real numbers), there is a possibility to do it for this special case.

One approach is to isolate separate AM-GM inequalities for pairs of numbers that happen to have the same arithmetic means as the whole list. So if for every pair $(i,j)$ with $1\leq i<j\leq n$ and $i+j=n+1$, one can prove their AM-GM inequality, that is $\frac{i+j}2\geq\sqrt{ij}$ which can be rewritten $(\frac{n+1}2)^2\geq ij$, then all of these can be multiplied together for $i=1,2,\ldots,\lfloor\frac n2\rfloor$, and with an extra trivial $\frac{n+1}2\geq\lceil\frac n2\rceil$ in case $n$ is odd, to give, for all $n\geq1$, that $(\frac{n+1}2)^n\geq n!$ with strict inequality for $n>1$. (The final result is also true for $n=0$, with equality, but I don't think the argument works well for that case since averages of an empty set or are not defined.)

So can we prove combinatorially that for positive integers $i<j$ one always has $(i+j)^2\geq4ij$ (which is obtained from $\frac{i+j}2\geq\sqrt{ij}$ by doubling and squaring both members)? Algebraically this is obvious since $(i+j)^2-4ij=(j-i)^2\geq0$, and with a bit of fiddling one can deduce, with $[m]$ denoting a model $m$-element set like $\{1,2,\ldots,m\}$, an injective map from a $[2]\times[2i]\times[j]\to[i+j]^2$ whose image is the complement of $[j-i]^2$ in $[i+j]^2$. For instance one can map $(1,a,b)\mapsto(j-i+a,b)$ (with $0<a\leq 2i$ and $0<b\leq j$), and then, for the same set of values $a,b$, map $(2,a,b)\mapsto(b,j-i+a)$ whenever at least one of the conditions $a>i$ or $b\leq j-i$ is met, and finally for the remaining cases, map $(2,a,b)\mapsto(j+a,i+b)$ for $0<a\leq i$ and $j-i<b\leq j$. Making a small picture will facilitate understanding the shuffling around that is going on here.

I won't go into the rather mundane details of how all these injections can be combined to given one great injection $[2]^n\times([1]\times[2]\times\cdots\times[n])\to[n+1]^n$ to complete the construction. It is of course questionable whether this combinatorial argument really sheds any new light on the inequality, since we essentially used algebra to get the idea for the basic injections; but anyway there it is.