2
$\begingroup$

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.

Thanks!

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

Improve this question
$\endgroup$
3
  • $\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$
    – Gerhard Paseman
    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$
    – Emil Jeřábek
    Jun 21, 2011 at 18:17
  • $\begingroup$ @Emil, this was an error. I meant "polynomially tight" $\endgroup$
    – David Harris
    Jun 21, 2011 at 18:27

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ This formula works great. Thanks so much! $\endgroup$
    – David Harris
    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$
    – Gerhard Paseman
    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$
    – Gerhard Paseman
    Jun 21, 2011 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.