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?
Best Answer
The answer from mathlove gives several equality counter-examples to your conjecture. I prove below that changing your conjecture's $\lt$ to $\le$ is sufficient to make it correct.
As for your proof, the left part of your expression in step $(3)$ is
$$v_p\left(\frac{(x+n)!}{(x!)\operatorname{lcm}(x+1,\dots,x+n)}\right) = \sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}-1\right\rfloor \tag{1}\label{eq1A}$$
With $i$ large enough so $p^i \gt n$, then $-1 \lt \frac{n}{p_i} - 1 \lt 0 \implies \left\lfloor\frac{n}{p^i}-1\right\rfloor = -1$. Thus, $\sum_{i=1}^{\infty}\left\lfloor\frac{n}{p^i}-1\right\rfloor = -\infty$. Also, I believe your note of "It is based on $n$ instead of $x+n$ because $p^t$ is necessarily less than $n$" means you tried using
$$\left\lfloor\frac{x+n}{p^{i}}\right\rfloor - \left\lfloor\frac{x}{p^{i}}\right\rfloor = \left\lfloor\frac{n}{p^{i}}\right\rfloor \tag{2}\label{eq2A}$$
However, even with your restriction, this is not always true. For example, with $t = i = 1$, $p = 3$, $n = 4$ and $x = 5$, the left side of \eqref{eq2A} becomes $\left\lfloor\frac{9}{3}\right\rfloor - \left\lfloor\frac{5}{3}\right\rfloor = 3 - 1 = 2$ while the right side becomes $\left\lfloor\frac{4}{3}\right\rfloor = 1$.
In addition, I assume the $-1$ term on the right side in \eqref{eq1A} comes from the $\operatorname{lcm}$ having its exponent of $p$ be the maximum among the prime factorizations of the integers in $[x+1,x+n]$. However, the $-1$ term should only be used up to that exponent, not to $\infty$, since this causes the sum in \eqref{eq1A} to go to $-\infty$, as I explained earlier.
I don't see any direct way to use what you're trying to do. Instead, your conjecture's $\leq$ version can be proven using an equivalent form of your inequality,
$$\begin{equation}\begin{aligned} \frac{(x + n)!}{(x!)\operatorname{lcm}(x + 1, \, \ldots, \, x + n)} & \le (n-1)! \iff \\ \frac{(x + n)!}{(x!)(n-1)!} & \le \operatorname{lcm}(x + 1, \, \ldots, \, x + n) \iff \\ n\left(\frac{(x + n)!}{(x!)(n!)}\right) & \le \operatorname{lcm}(x + 1, \, \ldots, \, x + n) \iff \\ n\binom{x + n}{n} & \le \operatorname{lcm}(x + 1, \, \dots, \, x + n) \end{aligned}\end{equation}\tag{3}\label{eq3A}$$
Note this form is related to that in your question Reasoning about least common multiples and their relationship to binomial coefficients, and my answer there is also fairly similar to this proof. First, for somewhat simpler algebra, let
$$b = \binom{x + n}{n}, \; c = \operatorname{lcm}(x + 1, \, \dots, \, x + n) \tag{4}\label{eq4A}$$
Using the prime factorization exponents based on the definition of $\operatorname{lcm}$, and the $p$-adic order function, then for any prime $p$, let
$$d = \nu_{p}(n) \tag{5}\label{eq5A}$$
$$e = \nu_{p}(b) \tag{6}\label{eq6A}$$
$$f = \nu_{p}(c) = \max_{x + 1 \, \le \, i \, \le x + n}(\nu_{p}(i)) \tag{7}\label{eq7A}$$
By proving
$$d + e \le f \tag{8}\label{eq8A}$$
for all primes $p$, then \eqref{eq3A} will be true. There are $2$ basic cases to consider:
Case #$1$: $e = 0$
Since $[x + 1, x + n]$ is a set of $n$ consecutive integers, they represent a complete residue system of integers modulo $n$, so there's a $1 \le i \le n$ where $x + i \equiv 0 \pmod n \implies x + i = kn, \; k \in \mathbb{N}$. Thus, for this $i$ and $k$,
$$d = \nu_p(n) \le \nu_p(kn) = \nu_p(x + i) \le f \tag{9}\label{eq9A}$$
which shows \eqref{eq8A} holds.
Case #$2$: $e > 0$
Note Kummer's theorem states $e$ (as defined in \eqref{eq6A}) is the number of carries when $x$ is added to $n$ in each prime base $p$. Thus, there must be at least one carry in this case.
Define for any integer $y \ge 0$ it's standard base $p$ representation as
$$y = \sum_{i=0}^{\infty}a_i p^{i}, \; 0 \le a_i \le p - 1 \tag{10}\label{eq10A}$$
and the following function to specify the requested digit
$$g(y, i) = a_i \tag{11}\label{eq11A}$$
Thus, from \eqref{eq5A},
$$g(n, i) = 0 \; \forall \; 0 \le i \le d - 1 \tag{12}\label{eq12A}$$
i.e., the lowest $d$ digits of $n$ in base $p$ are $0$. This means none of these digits can be involved in a carry when $x$ is added to $n$, so the first possible such digit is $g(n, d)$. Since there's at least one carry, there's a maximum index involved. Let $h \ge d$ be the index of the digit where the highest carry comes from. This means the next higher index digit is increased by $1$, i.e.,
$$\begin{equation}\begin{aligned} & g(n + x, h + 1) = g(n, h + 1) + g(x, h + 1) + 1 \implies \\ & g(n + x, h + 1) \ge g(x, h + 1) + 1 \end{aligned}\end{equation}\tag{13}\label{eq13A}$$
Note $g(n, h + 1) + g(x, h + 1) + 1 \lt p$ because it can't require a carry since index $h$ is where the highest index of any carry comes from. Also, \eqref{eq13A} shows there's an integer in $[x + 1, x + n]$ where the coefficient at index $h + 1$ increases by $1$ to $g(n + x, h + 1)$, so all lower coefficients then are $0$, i.e., there's a $1 \le i \le n$ where
$$g(n + i, j) = 0 \; \forall \; 0 \le j \le h \implies \nu_p(n + i) \ge h + 1 \tag{14}\label{eq14A}$$
Using \eqref{eq7A}, this means
$$\nu_p(n + i) \le f \implies h + 1 \le f \tag{15}\label{eq15A}$$
The carries occurred only in the digits with indices between $d$ and $h$, inclusive, so the number of carries, i.e., $e$ (as Kummer's theorem mentioned earlier shows), is less or equal to the number of indices in that range. This gives
$$e \le h - d + 1 \implies d + e \le h + 1 \tag{16}\label{eq16A}$$
Putting \eqref{eq15A} and \eqref{eq16A} together gives \eqref{eq8A}.