4

I am looking for a nice argument which shows that $$\left|\,(1-x)(2-x)(3-x)\cdots(n-x)\,\right| < n!$$ for all $0 < x < n+1$.

I've proven it already (cases based on the integer part of $x$), but am unsatisfied with my proof.

My proof, by request: If $x \in \mathbb{Z}$ then the LHS is zero. Therefore, let $k < x < k+1$ with $0 \leq k \leq n$ and $k \in \mathbb{Z}$. Then $$\begin{align} &|(1-x)(2-x)(3-x)\cdots(n-x)| \\ &< |1-(k+1)| |2-(k+1)| \cdots |k-(k+1)|\,|(k+1)-k||(k+2)-k| \cdots |n-k| \\ &= |k||k-1| \cdots |1| \, |1| |2| \cdots |n-k| \\ &= |1| |2| \cdots |n-k| \, |1| \cdots |k-1| |k| \\ &\leq |1| |2| \cdots |n-k| |n-k+1| \cdots |n| \\ &= n! \end{align}$$

I suspect there's a much nicer way to approach the problem, but I can't seem to find one. Any help is much appreciated!

Samuel Li
  • 785
  • 2
    Induction ought to work – Mad Physicist Oct 02 '18 at 01:16
  • I thought of induction but dismissed it since the bound on $x$ depends on $n$ as well. I may have been a bit hasty though, I'll try to see if it works out. – Samuel Li Oct 02 '18 at 01:18
  • 1
    Assume the first n-1 terms give < (n-1)!. Show that n-x < n and then that 1-x < 1! – Mad Physicist Oct 02 '18 at 01:18
  • 4
    You should provide the proof you described, so that people don't waste their precious time duplicating your effort. Moreover, it will help to know what you consider an "unsatisf[ying]" solution. – Blue Oct 02 '18 at 01:28
  • 1
    @MadPhysicist Perhaps I'm misunderstanding what you're saying. I can't see how we can assume that the first $n-1$ terms give $<(n-1)!$, since we don't necessarily have $0 < x < n$ when trying to prove the statement for $n+1$. If there's an easy way to work around this, I don't see it, unfortunately. – Samuel Li Oct 02 '18 at 01:39
  • By induction. The conclusion holds for $n =1$. Suppose that the conclusion holds for $n -1$. We need to check it for $n$. If $0< x < n$ then by induction assumption, we have |(1-x)\cdots (n-1-x)|< (n-1)!. Since $0< x < n$ then $n-x < n$, hence the conclusion holds. If $x =n$, the conclusion holds since the RHS is $0$. If $n< x < n+1$, put $y =n+1-x \in (0,1)$, we have $$|(1-x) \cdots (n-x)| = |(y-n) \cdots (y-1)| =|(1-y) \cdots (n-y)|.$$ Hence, we come back to the case $0< x < n$. – nguyen0610 Oct 02 '18 at 01:52
  • Can I just add, I actually quite like your proof? – Theo Bendit Oct 02 '18 at 01:57
  • I could give a visual incomplete answer. All you have to do is prove that the graph of the polynomial $y = (1-x)(2-x)\dots(n-x)$, when viewed in the window $0 < x < n+1$, is bounded from above by the line $y = n!$ and below by the line $y = -n!$. All our zeros to this polynomial are contained in this window. The boundary $x = 0$ and $x = n+1$ evaluate to either $y = n!$ or $y = -n!$ (think about the direction of the tails of the polynomial). However, and I'm interested in this, all I'd have to do now is show you that the local mins and maxes don't cross $y = n!$ or $y = -n!$, which I don't – DWade64 Oct 02 '18 at 02:35
  • know how to do. It would be interesting to know if a general theorem on the "size of the peaks of a polynomial" exists out there from the polynomial itself (any bounds on the peaks?). You could just take derivatives. But that would not work here – DWade64 Oct 02 '18 at 02:37
  • 1
    @DWade64 Yes - part of the reason I suspect there's a much nicer proof is that the $n!$ bound is very weak; for 1 < x < n, the LHS comes nowhere near $n!$. A much stronger bound (depending in a simple way on $x$) should exist, but I haven't found one yet. – Samuel Li Oct 02 '18 at 18:59
  • @SamuelLi: So you are looking for a stronger bound, not for a nicer proof. That would be useful information to be added to the question. – Martin R Oct 03 '18 at 07:33

3 Answers3

2

Suppose

$$ \mid (1-x) (2-x) \cdots (n-x) \mid < n! $$

for all $0 < x< n+1$.

If $0< x < n+1$, then

$$ \mid (1-x) (2-x) \cdots (n-x) (n+1-x) \mid < n! \mid n+1-x \mid < (n+1)! $$

If $n+1<x<n+2$, then let $y=x-1$ so $n<y<n+1$

$$ \mid (1-x) (2-x) \cdots (n-x) (n+1-x) \mid = \mid (-y) (1-y) (2-y) \cdots (n-y) \mid \\ = \mid y \mid \mid (1-y) (2-y) \cdots (n-y) \mid\\ < \mid y \mid n!\\ < (n+1)! $$

That was the induction step, let's go back to the base case.

$$ 0 < x < 0+1\\ 0 < 1-x < 1\\ \mid (1-x) \mid = (1-x) < 1!=1 $$

AHusain
  • 5,183
2

You can use induction here, due to the symmetry of the expression.

Suppose that $$\left|(1-x)(2-x)(3-x)\cdots(n-1-x)\right| < (n-1)!$$ for $0 < x < n$.

Then if $0 < x < n$, we have $|n-x|< n$, so $$|(1-x)(2-x)(3-x)\cdots(n-x)| < n!$$ by the inductive hypothesis.

And if $n\le x<n+1$, put $y=n+1-x$; now $0<y\le 1$, so we can use the inductive hypothesis on $y$, to get $$|(1-y)(2-y)(3-y)\cdots(n-y)| < n!$$ But $|(1-y)(2-y)(3-y)\cdots(n-y)|$ is just $|(1-x)(2-x)(3-x)\cdots(n-x)|$, with the terms reversed, so we are done.

TonyK
  • 64,559
  • D'oh! Never thought to use the symmetry of the problem to patch the inductive proof. I think this is akin to what I was looking for. – Samuel Li Oct 03 '18 at 12:38
1

What you have is a nice, direct proof. I would only get rid of the absolute values, so that it becomes more obvious how each term is estimated.

So for $x \in (k, k+1)$ with an integer $k$, $0 \le k \le n$, we have $$ |(1-x)(2-x)(3-x)\cdots(n-x)| \\ = (x-1)(x-2)\cdots(x-k) \, \times \, (k+1-x)(k+2-x) \cdots (n-x) \\ < (k)(k-1)\cdots (1) \, \times \, (1)(2) \cdots(n-k) \, . $$ In the second part of the product we can increase each factor by $k$, so that the expression is $$ \le (k)(k-1)\cdots (1) \, \times \, (k+1)(k+2) \cdots(n) = n! \, . $$

Alternatively use that $$ (k)(k-1)\cdots (1) \, \times \, (1)(2) \cdots(n-k) = k!(n-k)! = \frac{n!}{\binom nk} \le n! \, . $$

Martin R
  • 113,040
  • More simply: the product is less than $m!(n-m)!$ and that is at most $n!$ because $1 \le \binom{n}{m} = n!/(m!(n-m)!)$. – marty cohen Oct 02 '18 at 06:20
  • @martycohen: I have added it now, thanks for the suggestion. (I found the direct approach simpler – you would need a similar argument to show that $\binom nm \ge 1$). – Martin R Oct 02 '18 at 07:02
  • I never noticed the possibility of using ${n \choose m}$ to bound the final result, and find it quite nice! Unfortunately I could only accept one answer, but an upvote to you. – Samuel Li Oct 03 '18 at 12:37