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
    Commented 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
    Commented Jun 21, 2011 at 18:17
  • $\begingroup$ @Emil, this was an error. I meant "polynomially tight" $\endgroup$
    – David Harris
    Commented 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
    Commented 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
    Commented 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
    Commented Jun 21, 2011 at 19:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .