4
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Induction ought to work $\endgroup$ – Mad Physicist Oct 2 '18 at 1:16
  • 1
    $\begingroup$ Assume the first n-1 terms give < (n-1)!. Show that n-x < n and then that 1-x < 1! $\endgroup$ – Mad Physicist Oct 2 '18 at 1:18
  • 4
    $\begingroup$ 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. $\endgroup$ – Blue Oct 2 '18 at 1:28
  • 1
    $\begingroup$ @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. $\endgroup$ – Samuel Li Oct 2 '18 at 1:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Samuel Li Oct 2 '18 at 18:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Samuel Li Oct 3 '18 at 12:38
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)!)$. $\endgroup$ – marty cohen Oct 2 '18 at 6:20
  • $\begingroup$ @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$). $\endgroup$ – Martin R Oct 2 '18 at 7:02
  • $\begingroup$ 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. $\endgroup$ – Samuel Li Oct 3 '18 at 12:37

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.