2
$\begingroup$

Let $x>0, n>0$ be integers.

Let LCM$(x+1, x+2, \dots, x+n)$ be the least common multiple of $x+1, x+2, \dots, x+n$.

Let $v_p(u)$ be the highest power of $p$ that divides $u$.

It seems to me that:

$$\frac{(x+1)(x+2)\times\dots\times(x+n)}{\text{LCM}(x+1, x+2, \dots, x+n)} \le (n-1)!$$

Here is my thinking:

  • Let $p$ be any prime that divides $(x+1)\times\dots\times(x+n)$.

  • Let $x+i$ be the integer in $\{x+1,x+2. \dots, x+n\}$ that is divisible by the highest power of $p$.

  • All integers in the sequence $\{x+1, x+2, x+3, \dots, x+n\}$ that are divisible by $p$ will have the form $x + i \pm ap$ where $0 < a \le \left\lfloor\dfrac{n-1}{p}\right\rfloor$.

  • $v_p\left(\dfrac{(x+1)(x+2)\times\dots\times(x+n)}{\text{LCM}(x+1,x+2,\dots,x+n)}\right) \le v_p(p) + v_p(2p) + \dots + v_p\left(\left\lfloor\dfrac{n-1}{p}\right\rfloor p\right) = v_p((n-1)!)$

  • So, it follows that the maximum power of $p$ that divides $\dfrac{(x+1)\times\dots\times(x+n)}{\text{LCM}(x+1,\dots,x+n)}$ is less than or equal to the maximum power of $p$ that divides $(n-1)!$


Edit: Made changes to third and fourth bullet point with an attempt to make them cleaner.

Based on feedback received.


Edit 2: I originally put the "same" power in the last bullet point. That is not correct. It should be less or equal. I have changed it.


Edit 3: Fixed a typo. n! should be (n-1)!.

$\endgroup$
  • $\begingroup$ Are the third and fourth parts in your thinking saying that $v_p((x+1)\cdots (x+n))\le v_p(x+i)+\lfloor\frac{n-1}{p}\rfloor$ ? If not, can you make it clearer? $\endgroup$ – mathlove Sep 20 '18 at 7:13
  • $\begingroup$ @mathlove, thanks for the feedback. I have cleaned up the text in the question. I hope that my thinking is now clearer. $\endgroup$ – Larry Freeman Sep 21 '18 at 15:03
  • $\begingroup$ OK, I'll read them carefully. By the way, the last bullet point is not true in general. Take $x=1,n=9,p=2$. $\endgroup$ – mathlove Sep 21 '18 at 15:24
  • $\begingroup$ Very good point. The maximum power is less or equal not necessarily the same. I will update the argument. $\endgroup$ – Larry Freeman Sep 21 '18 at 15:46
  • $\begingroup$ Interpreted literally, the third bullet point is not ture. Take $x=3,n=3,p=2$. Then, $x+i-p$ is not in $\{x+1,\cdots, x+n\}$. Also, in the fourth bullet point, the equation $v_p(p) + v_p(2p) + \dots + v_p\left(\left\lfloor\dfrac{n-1}{p}\right\rfloor p\right) = v_p(n!)$ is not true. Take $n=8,x=1,p=2$. $\endgroup$ – mathlove Sep 22 '18 at 4:09
1
$\begingroup$

Your claim is true according to a wiki page.

Changing $n,k$ to $x+n,n-1$ respectively in$$\binom nk\le\frac{\text{LCM}(n-k,n-k+1,\cdots, n)}{n-k}$$ we get $$\binom{x+n}{n-1}\le\frac{\text{LCM}(x+1,x+2,\cdots, x+n)}{x+1}$$ which is your claim.

$\endgroup$

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.