2
$\begingroup$

Is it correct that for any positive integers $x,n$, that $\frac{(x+n)!}{(x!)\text{lcm}(x+1, \dots, x+n)} < (n-1)!$ where lcm is the least common multiple.

I ask because I find this relationship very interesting but I haven't seen it stated in this form.

I have seen a related inequality that:

$$\frac{\text{lcm}(x,x+1, \dots, x+n)}{x} \ge {{x+n}\choose{n}} = \frac{(x+n)!}{x!n!} $$

Which rearranges to this:

$$\frac{n!}{x} \ge \frac{(x+n)!}{(x!)\text{lcm}(x,x+1,\dots,x+n)}$$

Or even closer:

$$n! \ge \frac{(x+n)!}{((x-1)!)\text{lcm}(x,x+1,\dots,x+n)}$$

So that:

$$n! \ge \frac{(x+n)!}{(x!)\text{lcm}(x+1,\dots,x+n)}$$

This appears to me to be a stronger result than the one I am asking about. I am not clear how to derive my result from this stronger result.

On the other hand, I am able to justify my result independently of this equation. Here's my argument:

(1) Let $f_n(x) = \dfrac{(x+n)!}{(x!)\text{lcm}(x+1, \dots, x+n)}$

(2) No prime greater than $n-1$ divides $f_n(x)$ since:

Assume that a prime $p>n$ divides $x+c$ and $x+d$ with $0 < c < d \le n$. It follows that $p | (x+d - x+c) = d - c < n$ which is impossible.

(3) For each prime $p < n$ that divides $f_n(x)$, we can use Legendre's Formula to get this result (since we are dividing by the least common multiple):

$$v_p\left(\frac{(x+n)!}{(x!)\text{lcm}(x+1,\dots,x+n)}\right) = \sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}-1\right\rfloor < v_p((n-1)!) = \sum_{i=1}^{\infty}\left\lfloor\frac{n-1}{p^i}\right\rfloor$$

where $v_p(x)$ is the largest power of $p$ that is less than or equal to $x$

Note: It is based on $n$ instead of $x+n$ because $p^t$ is necessarily less than $n$

Is my reasoning correct? Is there a straight forward way to derive this result from the first equation? Is the argument that I present using Legendre's Formula valid? If valid, can it be improved or simplified? If not valid, what was my mistake?

$\endgroup$
1
$\begingroup$

There are infinitely many counterexamples.

If $n=2$, then we get, for any $x$, $$f_2(x)=\frac{(x+2)!}{(x!)\text{lcm}(x+1, x+2)}=\frac{(x+2)!}{(x!)(x+1)(x+2)}=1\color{red}=(2-1)!$$

If $n=3$ and $x=2^k-1$ where $k$ is a positive integer, then since $$\text{lcm}(x+1,x+2,x+3)=2^{k-1}(x+2)(x+3)$$ we get $$f_3(2^k-1)=\frac{(x+1)(x+2)(x+3)}{\text{lcm}(x+1, x+2, x+3)}=\frac{2^k}{2^{k-1}}=2\color{red}=(3-1)!$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the counter examples! In each case $\sum\limits_{i=1}^{\infty} \left\lfloor\dfrac{n}{p^i}-1\right\rfloor = \sum\limits_{i=1}^{\infty} \left\lfloor\dfrac{n-1}{p^i}\right\rfloor$. Have you found any counter examples where this formula is wrong? I am wondering if changing $<$ to $\le$ addresses the counter examples. $\endgroup$ – Larry Freeman May 23 at 18:32
  • $\begingroup$ @Larry Freeman : Sorry for the late reply. No, I haven't. Have you proven $f_n(x)\color{red}{\le} (n-1)!$ in this question? $\endgroup$ – mathlove May 25 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.