Proof regarding factorials.

Question

Suppose $a$ and $k$ are positive integers, then how would you prove(not intuitively) that:

$a!k! \leq (ak)!$

Although it is apparent that the inequality is correct, but how can I show this algebraically?

Answer 1

Assume $a, k\geq1$.

\begin{align} \frac {(ak)!} {k!} &= (ak)(ak-1)\cdots(k+1) \\\\ a!&=a(a-1)\cdots2 \\\\ \implies \frac {(ak)!} {a!k!} &= \frac {(ak)(ak-1)\cdots(k+1)}{a(a-1)\cdots2} \geq 1 \end{align}

The numerator has $ak-(k+1)+1=(a-1)k$ terms, while the denominator has $a-1$ terms (which is the same or less by our assumption). Matching each term from the denominator with one from the numerator:

$$ak\geq a\\ ak-1\geq a-1\\ \vdots$$

you get the inequality.

Answer 2

$[1\cdot2\cdot3\dots k][(k+1)\cdot(k+2).\dots (2k)][(2k+1)\cdot(2k+2)\dots (3k)]\dots[(ak-k+1)\cdot(ak-k+2)\dots (ak)]$

$=k!a![(k+1)\cdot(k+2)\cdot\dots (2k-1)(k)][(2k+1)\cdot(2k+2)\dots (k)]\dots [(ak-k+1)\cdot(ak-k+2)\dots (k)]\ge k!a!$

I am taking $1$ from last term of the the first third bracket (1st group of k terms) $2$ from the last term of the 2nd third bracket(2nd group of k terms) , $3$ from the last term of the 3 rd third bracket(3rd group of k terms) and so on to form $a!$

For a more comprehensive answer look at this,

Divide the expression $(mn)!$ into m groups each group consisting of the nos. $\{(kn+1)(kn+2).....((k+1)n)\}$, here k runs from $0$ to $m-1$

So we have ,$\displaystyle (mn)!=\prod_{k=0}^{m-1}(kn+1)(kn+2).....((k+1)n)$

In each group first $n-1$ nos is divisible by $(n-1)!$ as we have m groups so the total product is divisible by $((n-1)!)^m$ (Using the fact that product of $k$ consecutive nos is divisible by $k!$)

Product of the last nos. of the group is $\displaystyle \prod_{k=0}^{m-1}(k+1)n=m!.n^m$

So the whole product is divisible by $((n-1)!)^m.m!.n^m=m!(n!)^m$

Hence proving the fact that $\displaystyle \frac{(mn)!}{m!(n!)^m}$ is an integer.

So $m!n!\le m!(n!)^m\le (mn)!$

Answer 3

If $a,k\gt1$ then $(a-1)(k-1)\gt0$; that is, $ak\gt a+k-1$. Since $a,k\in\mathbb{Z}$, we have $ak\ge a+k$.

As an element in Pascal's Triangle, $\displaystyle\frac{(a+k)!}{a!\,k!}=\binom{a+b}{a}\in\mathbb{Z}$, and since $ak\ge a+k$, we have $\dfrac{(ak)!}{(a+k)!}\in\mathbb{Z}$. Therefore, $$ \frac{(ak)!}{a!\,k!}=\frac{(a+k)!}{a!\,k!}\frac{(ak)!}{(a+k)!}\in\mathbb{Z}\tag{1} $$ Since $a!\,k!\mid(ak)!$ and $(ak)!\ne0$, we have that $a!\,k!\le(ak)!$.

Now all we have left to do is handle the case where $a$ or $k$ is $1$. In that case, $a!\,k!=(ak)!$, so we are done.