1
$\begingroup$

Let $x_1>1, x_2>1, \dots, x_n>1$ be $n$ distinct positive integers with the following properties:

Does it now follow that: $n^n < \prod\limits_{i=1}^n x_i$?

It seems to me that this should be provable through considering the minimal product that satisfies the condition.

Examples:

  • for $n=1$, $x_1 = 5$
  • for $n=2$, $x_1, x_2 = \{5, 7\}$
  • for $n=3$, $x_1, x_2, x_3 = \{5, 7, 11\}$

I am not clear how to proceed. One thought is to use induction for $n=1$ and then show that:

$$\prod\limits_{i=1}^{n+1} x_i - \prod\limits_{i=1}^n x_i\ge [(n+1)^{n+1} - (n+1)^n] + [(n+1)^n - n^n]$$

which gets me to this:

$$\left(\prod\limits_{i=1}^n x_i\right)(x_{n+1} - 1) > (n+1)^n(n) + \prod\limits_{k=0}^{n-1}{n \choose k}n^k = n^{n+1} + (n+1)\left(\prod\limits_{k=0}^{n-1}{n \choose k}n^k\right)$$

Is there a straight forward way to resolve this question? What would be a recommended way to proceed?

$\endgroup$
4
  • $\begingroup$ How are the $x_i$ defined? If $x_i$ is the greatest integer of the set you are considering, is $x_{i+1}$ the next integer that satisfies $\text{gcd}(x_{i+1}, 6)=1$? $\endgroup$
    – Dr. Mathva
    Sep 28 '20 at 20:24
  • $\begingroup$ Thanks for your question. I'm assuming that $x_i$ is in ascending order. I'll add this point to the question. $\endgroup$ Sep 28 '20 at 20:25
  • $\begingroup$ I am sorry to be so picky, but I imagine that you cannot choose, for example, $x_n=n^n+c$ such that $\text{gcd}(n^n+c,6)=1$ right? How does this follow from the definition? I imagine that, once you have $x_i$, you define $x_{i+1}$ as the smallest number bigger than $a_i$ such that $\text{gcd}(x_{i+1},6)$, right? $\endgroup$
    – Dr. Mathva
    Sep 28 '20 at 20:30
  • $\begingroup$ I appreciate the questions. :-). $n$ is just the number of elements. $x_i$ could $=n$ if gcd$(n,6) =1$. I am trying to find out if the value $n^n$ is lways less regardless of the $n$ distinct values chosen. A list of $n$ distinct i$x_i$ with the product less tgan $n^n$ would be a counter example. $\endgroup$ Sep 28 '20 at 20:46
2
$\begingroup$

Note that for $i$ odd we have $x_i=3i+2$ while for $i$ even we have $x_i=3i+1$. If we ignore those pesky $+2$s and $+1$s we have $$\prod\limits_{i=1}^n x_i\gt 3^nn!$$ while Stirling's approximation gives $$n^n \approx n!e^n\sqrt {2\pi n}$$ For $n \gt 25$ we have $\left(\frac 3e\right)^n \gt \sqrt{2 \pi n}$ so we just have to compute the values up through $n=24$ to see the claim is correct.

$\endgroup$
1
  • $\begingroup$ Thanks, Ross! Awesome. This is great! :-) $\endgroup$ Sep 28 '20 at 20:48
1
$\begingroup$

Let's use the following simple fact: all the integers $x$ that are coprime with $6$ may be represented as $x = 6k + r$, where $0 \le r < 6$ and $\gcd(r,6) = 1$. Since there are are only two such numbers $r$ ($1$ and $5$), the sequence $y_0,y_1,\dots$ given by $$ y_{2k} = 1 + 6k, \quad y_{2k + 1} = 5 + 6k $$ contains all the positive integers that are relatively prime with $6$.

Let's now order given numbers $1 < x_1 < x_2 < \dots < x_n$ and note that $$x_k \ge y_k > 3k \quad\quad k=1,\dots,n$$ and so we have inequality $$\prod_{k=1}^{n}x_k > \prod_{k=1}^{n}3k = 3^nn!.$$ Now let's prove that $$3^nn! > n^n\tag{*}$$ by induction. For $n = 1$ this is true. Suppose that (*) is holds for some $n$. Then $$ 3^{n+1}(n+1)! = 3(n+1)\cdot 3^n n! > 3(n+1)n^n > (n+1)\cdot (n+1)^n = (n+1)^{n+1}. $$ Here we use inequality $(n + 1)^n < 3 n^n$ given by monotonically increasing sequence $(1 + \frac{1}{n})^n \to e < 3$.

$\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.