Cfrgtkky

While investigating an integer sequence, I came across the following two OEIS entries:

• 
  A094331: Least k such that n! < (n+1)(n+2)(n+3)...(n+k).
  


• 
  A075357: a(n) = smallest k such that (n+1)(n+2)...(n+k) is just >= n!.
  

The generating rule for both of these sequences is basically identical, except A094331 uses $lt$ and A075357 uses $le$. This made me curious whether both sequences are actually identical (and I'm not the first; David Wasserman commented the same thing when he was adding more terms to A075357.) For the purposes of the OEIS, the sequences are technically different, because A094331(1) = 1 and A075357(1) = 0 (i.e. for $n=1$ and $k=0$, $frac{(n+k)!}{n!} = n!$.)

In approaching this problem, I first tried computational brute forcing. For values of $n$ from 2 to 1000000, $n ne k$. However, this approach is obviously limited. Since my ability in number theory is very weak, I was wondering if anyone with a greater knowledge of number theory may be able provide a definitive answer to this question.

By a theorem of Chebyshev, there exists for any integer $n > 1$ a prime $p$ with $n < p < 2n$. Hence $(2n)!$ and $(2n+1)$! are not perfect squares, since they're divisible by $p$ but not $p^2$. It follows that $(n+k)!/n! not = n!$ for any integers $n, k > 0$.

With the exception of $N=1$, $N!$ is never a square. This is because, by Bertrand's Postulate, there is always a prime between $N$ and $lfloor N/2rfloor$ (to be precise, a prime $p$ satisfying $lfloor N/2rfloorlt ple N$), and such a prime can only divide $N!$ once. So if we take $N=n+k$ with positive integers $n$ and $k$, we have $Ngt1$ and so $N!=(n+k)!$ is not a square. In particular, it cannot be the case that $(n+k)!=(n!)^2$. Thus it is never the case that $(n+k)!/n!=n!$.

It might be of interest to see if there is a proof that $N!$ is never the square of a factorial that doesn't rely on Bertrand's Postulate.

The only cases where those two sequences would differ would be when $n! = frac {(n+k)!}{n!}$ or $(n+k)! = (n!)^2$ and that is the only time you can have $n! le frac {(n+k)!}{n!}$ and $n! < frac {(n+k)!}{n!}$ not both be true or not both be false.

anomaly's answer explains why that can never for $n > 1$.

I just want to add that if $n = 1$ then this is $(k+1)! = 1$ which is true only if $k =0$.

Hence the sequences do differ at $n=1$. The first term of A075357 is $0$ while the term of A094331 is $1$. Otherwise the sequences are identical. But they do differ and $n=1$

So for A075357 you want the least $k$ so that $1! < frac {(1+k)!}{1!}$ and that is $1! = frac {1!}{1!}$ and $1! < frac {2!}{1!}$ and that is when $1+ k = 2$ or $k =1$. But of A094331 you want the least $k$ so that $1! le frac {(1+k)!}{1!}$ and because $1! = frac {1!}{1!}$ that is $1+k =1$ or $k = 0$.

As for any other $n > 1$ we have $frac {(n+k)!}{n!}ne n!$ we have $n! le frac {(n+k)!}{n!} iff n! < frac {(n+k)!}{n!}$ and the sequences are equal.