4
$\begingroup$

I am looking for someone to either point out a mistake or help me to improve the argument in terms of clarity, conciseness, and more standard mathematical argument.

Let $x$ be an integer such that $x, x+1, x+2, \dots, x+n-1$ is a sequence of consecutive integers.

Let $r_i$ be defined as:

$$r_i = \dfrac{x+i}{\gcd(x+i,x+i-2)\gcd(x+i,x+i-3)\dots\gcd(x+i,x+1)}$$

So, for example:

  • $r_0 = x$
  • $r_1 = x+1$
  • $r_2 = \dfrac{x+2}{\gcd(x+2,x)}$
  • $r_3 = \dfrac{x+3}{\gcd(x+3,x+1)\gcd(x+3,x)}$

Here's my intuition:

$$\frac{(x+n-1)!}{(x-1)!\prod\limits_{i < n}r_i} \le (n-1)!$$

For $x=a(n-1)!$, $\dfrac{(x+n-1)!}{(x-1)!\prod\limits_{i < n}r_i} = (n-1)!$ since:

$r_i = \dfrac{x+i}{i}$ since if there exists a prime $p$ that divides $x+i$ and also divides $x+j$ where $j < i$, then $p | (i-j)$ so that $p | x$ which gives $p | i$.

To complete the argument, I show that if the proposition is true of $x$, then it is also true of $\frac{x}{p}$.

For $r_i$:

  • if $p | (x+i)$ and $i < p$, it follows that this is the first time the prime is encountered $r_i$ remains the same as before.
  • if $p | (x+i)$ and $i > p$, it follows that $r_i = \frac{\text{prev}\_r_i}{p}$ and $r_p$ no longer has this value divided.
  • Let $r(x,n) = \prod\limits_{i < n}r_i$
  • Now, $\prod{r_i}$ depends on the number of integers that are divisible by $p$. if $p$ does not divide $x$, then the count of the integers divisible by $p$ is equal or less to the count when $p$ divides $x$ so that:

$r(x,n) \le r(\frac{x}{p},n)$

Does this complete the argument to show that:

$$\frac{(x+n-1)!}{(x-1)!r(x,n)} \le (n-1)!$$


Edit: My assumptions about each $r_i$ being relatively prime to each other is not correct. For example, consider: $36, 37, 38, 39, 40$

$r_0 = 36$ but $r_4 = 10$

For this reason, I removed the assumption about being relatively prime and primorials.

$\endgroup$
  • $\begingroup$ You wrote that $r_i$ is to be defined as $r_i = \dfrac{x+i}{\gcd(x+i,x+i-2)\gcd(x+i,x+i-3)\dots\gcd(x+i,x+1)}$. However, in the examples below it and based on the context of the rest of your question, it seems you are missing a factor of $\gcd(x+i,x)$ in the denominator. $\endgroup$ – John Omielan Aug 27 at 22:13
1
$\begingroup$

You are trying to prove

$$\frac{(x+n-1)!}{(x-1)!\prod\limits_{i < n}r_i} \le (n-1)! \tag{1}\label{eq1A}$$

With $x = a(n - 1)!$, you state that you get an equality in \eqref{eq1A}, with this being due to

$r_i = \dfrac{x+i}{i}$ since if there exists a prime $p$ that divides $x+i$ and also divides $x+j$ where $j < i$, then $p | (i-j)$ so that $p | x$ which gives $p | i$.

The statement starting from "if there exists ..." is correct, but your conclusion that $r_i = \dfrac{x+i}{i}$ is not true for any composite $i$. This is because you do not account for the prime factor $p$ possibly occurring among all of the products more times than it occurs in $i$. In particular, if $i = jk$, with $1 \lt j, k \le i - 2$, then $\gcd(x + i, x + j) \ge j$, $\gcd(x + i, x + k) \ge k$ and $\gcd(x + i, x) = i$. The best case scenario occurs when $j = k$ and is prime, which means the denominator will always be $\ge ji$.

For example, let $n = 5$ and $a = 1$ so $x = a(n - 1)! = 4! = 24$. This gives

$$\begin{equation}\begin{aligned} r_4 & = \frac{x+4}{\gcd(x+4,x+2)\gcd(x+4,x+1)\gcd(x+4,x)} \\ & = \frac{x+4}{2(1)(4)} \\ & = \frac{x+4}{8} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Note that if your assumption $r_i = \frac{x + i}{i}$ were true, then the left side of \eqref{eq1A} would be

$$\begin{equation}\begin{aligned} \frac{(x+n-1)!}{(x-1)!\prod\limits_{i < n}r_i} & = \frac{\prod\limits_{i=0}^{n-1}(x + i)}{x\prod\limits_{i=1}^{n-1}\frac{x + i}{i}} \\ & = \frac{\prod\limits_{i=0}^{n-1}(x + i)}{\left(\frac{\prod\limits_{i=0}^{n-1}(x + i)}{\prod\limits_{i=1}^{n-1}i}\right)} \\ & = (n - 1)! \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

so that part of your statement is correct. However, with my counter-example, since the denominator is $\frac{1}{2}$ of what is used in \eqref{eq3A}, you get a result of $2(n-1)! = 48$ instead, so \eqref{eq1A} is not true in that case.

| cite | improve this answer | |
$\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.