Suppose $d$ is a constant $< n^2$, and $m > n$. I have a kind of factorial function where I subtract $d$ from each pair of terms.

Is there any simple upper bound on $$ P = ( m (m-1) - d) \times ( (m-2) (m-3) - d ) \times \cdots \times \times ((n+1) n - d) $$

I only need an polynomially tight upper bound. If it makes it easier, you can assume $m = cn$ for $c$ close to 2.

The best I can come up with is $$ P \leq \Bigl( \frac{m (m-1) - d}{m (m-1)} \Bigr)^{(m-n)/2} m!/n! $$ but I don't think this is tight.


EDIT: Previous version incorrectly stated "exponentially tight" vs "polynomially tight"

  • $\begingroup$ You could pretend it is the product of m-n terms, half of them like m+k+sqrt(d) +1/2, the rest with a -sqrt(d) instead of +. Gerhard "Email Me About System Design" Paseman, 2011.06.21 $\endgroup$ Jun 21, 2011 at 18:14
  • $\begingroup$ What do you mean by an “exponentially tight” upper bound? Your bound (as well as the trivial bound $m!/n!$) is tight up to a factor of $2^{O(m)}$, isn’t it? $\endgroup$ Jun 21, 2011 at 18:17
  • $\begingroup$ @Emil, this was an error. I meant "polynomially tight" $\endgroup$ Jun 21, 2011 at 18:27

1 Answer 1


Edit. Of course, I would find the mistake after posting. k ranges over the even numbers from 2 to 2h, so the result is not as nice. I will try rescuing the approach. End Edit

Each term is close to (m- k+ sqrt(d) + 1/2)(m - k- sqrt(d) + 1/2), where k ranges from 1 to h=(m-n)/2. (h may be off by 1.) Your product is close to n! squared times the product of two binomial coefficients: m+ a choose h and m- b choose h, where a anb are close to sqrt(d). Letting a and b range over floor(sqrt(d)) and ceil(sqrt(d)) are a start if h is not too small. For finer estimates, let a and b be appropriate real numbers.

Gerhard "Email Me About System Design" Paseman, 2011.06.21

  • $\begingroup$ This formula works great. Thanks so much! $\endgroup$ Jun 21, 2011 at 19:03
  • $\begingroup$ One can rescue it by dividng by 2^h and multiplying by 2^h, but that is not very satisfying. Gerhard "Can Not Get No Satisfaction" Paseman, 2011.06.21 $\endgroup$ Jun 21, 2011 at 19:16
  • $\begingroup$ David, I am glad you like the approach. To make up for my earlier mistake, I offer to do a sanity check on any formula you post here addressing the problem and based on the method I suggested. Good luck. Gerhard "Email Me About System Design" Paseman, 2011.06.21 $\endgroup$ Jun 21, 2011 at 19:33

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.