Proof that the power of $2$ in $(3n)!$ is greater than or equals to the power of $2$ in $n!(n+1)!(n+2)!$

Question

Proof that the power of $2$ in $(3n)!$ is greater than or equals to the power of $2$ in $n!(n+1)!(n+2)!$.

I tried doing some algebraic manipulation,

$\frac{(3n)!}{n!(n+1)!(n+2)!}=\binom{(3n)!}{(n+2)!}\frac{(2n-2)!}{(n+1)!n!}=\binom{(3n)!}{(n+2)!}\binom{(2n-2)!}{(n+1)!}\frac{(n-3)!}{n!}=\binom{(3n)!}{(n+2)!}\binom{(2n-2)!}{(n+1)!}\frac{1}{(n-2)(n-1)n}$

Here, $\binom{(3n)!}{(n+2)!}$ and $\binom{(2n-2)!}{(n+1)!}$ are integers but $\frac{1}{(n-2)(n-1)n}$ is creating problems.

My argument is that some powers of $2$ from $\binom{(3n)!}{(n+2)!}$ and $\binom{(2n-2)!}{(n+1)!}$ would cancel out the powers of $2$ from $\frac{1}{(n-2)(n-1)n}$. But the argument is too ambiguous to be written down as a "proof".

Please let me know if there's a better way to approach these kinds of problems.

Any help would be highly appreciated.

Answer 1

The claim is true for $n \ge 3$. As observed in the comments above it is false for $n = 1$ and $n = 2$.

We can apply Legendre's Formula in its alternate form for $p=2$:

$$\nu_2(n!)=n-s_2(n)$$

where $\nu_2(n)$ is the exponent of the largest power of $2$ that divides $n$ and $s_2(n)$ is the sum of the digits in the binary representation of $n$.

We will use the following facts for $a$ and $b$ positive integers:

• $s_2(a+b) \le s_2(a) + s_2(b)$: it can be shown for example using Legendre's formula for $a+b \choose b$: $0 \le \nu_2({a+b \choose b}) = a+b-s_2(a+b)-b +s_2(b)-a+s_2(a)$;
• $s_2(2a) = s_2(a)$;
• $s_2(2a+1) = s_2(a)+1$;
• $(eq. 1)$ $\nu_2((3n)!)-\nu_2(n!)-\nu_2((n+1)!)-\nu_2((n+2)!)=3n-s_2(3n)-n+s_2(n)-n-1+s_2(n+1)-n-2+s_2(n+2)=s_2(n)+s_2(n+1)+s_2(n+2)-3-s_2(3n)$

We divide the problem for $n$ even and odd:

1. $n = 2k+1$, $k \ge 1$

$$s_2(n)=s_2(2k+1)=s_2(k)+1$$ $$s_2(n+1)=s_2(2k+2)=s_2(2(k+1))=s_2(k+1)$$ $$s_2(n+2)=s_2(2k+3)=s_2(2(k+1)+1)=s_2(k+1)+1$$ $$s_2(3n)=s_2(6k+3)=s_2(2(3k+1)+1)=s_2(3k+1)+1=s_2(k+1+2k)+1 \le s_2(k+1)+s_2(2k)+1=s_2(k+1)+s_2(k)+1$$

and putting them together ($(eq. 1)$) it is enough to show that:

$$s_2(k)+2s_2(k+1)+2-3 \ge s_2(k+1) + s_2(k) + 1$$

i.e. $s_2(k+1) \ge 2$, which is true except for $k=2^m-1$, $m \ge 1$. In that case $n=2^{m+1}-1$ and:

$$s_2(n)=m+1$$ $$s_2(n+1)=1$$ $$s_2(n+2)=2$$ $$s_2(3n)=s_2(3 \cdot (2^{m+1}-1))=s_2(2^{m+2}+2^{m+1}-4+1)=s_2(2^{m+2}+4 \cdot (2^{m-1}-1)+ 1)= 1+m-1+1 = m+1$$

and combining them we need to show that:

$$m+4-3 \ge m+1$$

which is true.

2. $n = 2k$, $k \ge 2$

$$s_2(n)=s_2(2k)=s_2(k)$$ $$s_2(n+1)=s_2(2k+1)=s_2(2k)+1=s_2(k)+1$$ $$s_2(n+2)=s_2(2k+2)=s_2(2(k+1))=s_2(k+1)$$ $$s_2(3n)=s_2(6k)=s_2(3k)=s_2(2k+k) \le s_2(2k)+s_2(k) = 2 s_2(k)$$

and putting them together ($(eq. 1)$) it is enough to show that:

$$2s_2(k)+1+s_2(k+1)-3 \ge 2s_2(k)$$

i.e. again $s_2(k+1) \ge 2$, which is true except for $k=2^m-1$, $m \ge 2$. In that case $n=2^{m+1}-2$ and:

$$s_2(n)=s_2(2^{m+1}-2)=s_2(2^m-1)=m$$ $$s_2(n+1)=s_2(2^{m+1}-1)=m+1$$ $$s_2(n+2)=s_2(2^{m+1})=1$$ $$s_2(3n)=s_2(3 \cdot (2^{m+1}-2))=s_2(3 \cdot (2^{m}-1))=s_2(2^{m+1}+2^{m}-4+1)=s_2(2^{m+1}+4 \cdot (2^{m-2}-1)+ 1)= 1+m-2+1 = m$$

and combining them we need to show that:

$$2m+2-3 \ge m$$

i.e.

$$m \ge 1$$

which is true.

See also this linked question.

Answer 2

For $n=1$ it's wrong, but for $n=2$ it's true.

Let $$(3n)!\geq n!(n+1)!(n+2)!$$ for $n\geq2$.

Thus, $$(3n+3)!=(3n+1)(3n+2)(3n+3)(3n)!\geq$$ $$\geq(3n+1)(3n+2)(3n+3)n!(n+1)!(n+2)!\geq(n+1)!(n+2)!(n+3)!,$$ where the last inequality it's $$(3n+1)(3n+2)(3n+3)\geq(n+1)(n+2)(n+3),$$ which is obvious.

Now, use an induction, id est, the following reasoning.

Let $P(n)$ says $(3n)!\geq n!(n+1)!(n+2)!$ for any natural $n\geq2$.

We proved that:

1. $P(2)$ is true;
2. For any $n\geq2$ $P(n)\Rightarrow P(n+1)$ is true.

Thus, by the mathematical induction $P(n)$ is true for any $n\geq2$, which we needed to prove.