Proof for a multi-index inequality?

207 Views Asked by At

Say I have a multi-index $\alpha = (\alpha_1, \alpha_2, \ldots, \alpha_n)$ consisting of $n$ terms, where $\alpha_n\in\mathbb{N}$ whose modulus is $|\alpha| = \alpha_1 + \alpha_2 + \ldots + \alpha_n$.

Can I say the following inequality / majorisation always hold? How to prove it?

$$\large \alpha! \leq 2^{n\cdot |\alpha|!}$$

Where the multi-index factorial is defined as $\alpha! = \alpha_1!\cdot \alpha_2!\cdot \cdots \alpha_n!$ and $|\alpha|! = (\alpha_1 + \alpha_2 + \ldots + \alpha_n)!$

I tried to manipulate a bit with the logarithm, getting nothing serious, like

$$\frac{\sum_i \ln(\alpha_i!)}{\left(\sum_i \alpha_i\right)!} \leq n\ln(2)$$

Also I was wondering if we could improve the inequality by using $|\alpha !|$ instead of $|\alpha|!$, where $|\alpha!| = \alpha_1! + \alpha_2! + \ldots + \alpha_n!$

1

There are 1 best solutions below

0
On

I will try to answer my own question after a little pen&mind computation.

Let's start from the beginning, taking the logarithm of both sides $$\ln\left(\alpha!\right) \leq \ln\left(2^{n|\alpha|!}\right)$$ Now we use log properties and multi-index definitions.

$$\ln\left(\prod_i \alpha_i!\right) \leq \ln\left(2^{n\left(\sum_i \alpha_i\right)!}\right)$$

$$\sum_i \ln\left(\alpha_i!\right) \leq n\left(\sum_i \alpha_i\right)! \ln(2)$$

Remember that all the sums and the products are finite.

Now we divide both terms by $\prod_i \alpha_i!$

$$\frac{\sum_i \ln\left(\alpha_i!\right)}{\prod_i \alpha_i!} \leq n\color{red}{\frac{\left(\sum_i \alpha_i\right)!}{\prod_i \alpha_i!}}\ln(2)$$

Where I highlighted in red that term because that is nothing but the multinomial. Indeed (little stepback into combinatoric) the multinomial

$$(x_1+x_2+\cdots+x_n)!\over x_1!x_2!\cdots x_n!$$

counts the number of ways you can place $x_k$ objects into box $k$ for $1\le k\le n$. From here on we use another true inequality, that is:

$${(x_1+x_2+\cdots+x_n)!\over x_1!x_2!\cdots x_n!}\le n^{x_1+x_2+\cdots+x_n}$$

with equality only in trivial cases, where

$$n^{x_1+x_2+\cdots+x_n}$$

counts the number of ways you can assign a box to each object, which is equivalent to putting objects into boxes with no restriction on the number of objects that go into any of the boxes. With these interpretations the inequality holds true as shown above.

With this in mind, considering the $x_i$ are our $\alpha_i$, we can rewrite our inequality as

$$\ln\left(\prod_i \alpha_i!\right) \leq \prod_i \alpha_i! \ln(2) n^{1 + |\alpha|}$$

which means

$$\ln(\alpha!) \leq \alpha! n^{1 + |\alpha|}\ln(2)$$

Now it's always true that $n^{1 + |\alpha|} \geq n $ and the equality holds in the trivial case (a null multi-index). So exponentiating

$$\alpha! \leq 2^{\alpha!\cdot n^{1 + |\alpha|}}$$

namely

$$\alpha! \leq 2^{\alpha!\cdot n}$$

Since the same term $\alpha!$ appears both in the left side as a single term and in the right side as the argument of an exponential of base greater than $1$, and since we have always $n > 0$, this inequality holds true $\forall n \in \mathbb{N}$, $\forall \alpha$ multi-index, $\forall \alpha_i$ element of the multi-index since $\alpha_i$ is either $0$ or a natural number.

Improvement

We can see the last inequality is an improvement of the initial one, since the latter one is obvious and since $|\alpha|! \geq \alpha!$. This means that $$\alpha! \leq 2^{n\cdot \alpha!}$$

is stronger in the sense that it lows down the bigness of the majorisation. In layman words it's like to pass from saying $2 < 10$ to $2 < 4$.