Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In previous question, I asked how one would simplify the following equation for the case where the variables are very big:

$\sum\limits^{k}_{i=m}(N-i)^{k-i}(\frac{1}{N})^k\frac{k!}{(k-i)!i!} \leq a$

This answer was basically to use an approximation like Stirling's formula. Having implemented this with some code, it still takes too long to find the maximum value of N so that the inequality holds true. Therefore, I need a direct solution for N. So the new question is, how would you go about solving this equation for N?

(Some simplifications are acceptable, but I would like to have it as accurate as possible. The values this equation will be used for are all in the 100,000-1,000,000 range, except $m$, which is in the 100s range.)

share|improve this question
    
What can be said about m and k? Because if m were smal, the sum with m = 0 can be probably computed explicitely using exponential generating functions (e.g.f.) and then you can approximate only the first terms. Of course, if m is too big, this is not feasible. Also if k is too big, the solution with e.g.f. might not help you much. –  Marek Nov 12 '10 at 15:40

1 Answer 1

Now you are basically into root finding. I love Numerical Recipes. I have had the book over 30 years. Good discussion of the techniques and code supplied in various languages. Your formula should be an easy one. Other numerical analysis books will work, too.

A small thought: if m is as small as you say, there might be some algebraic simplification in making it 1. I haven't found it, but others are better at these combinatoric identities.

If you are actually doing the sum every time, you might be able to identify the range of i that is the big contribution. It looks like it should be somewhat below k/2. You can probably reduce the terms in the sum by a large factor, at least to get close to N. Then use the full formula for final refinement. And take the N^(-k) out of the sum.

share|improve this answer
    
I've finally been able to get the book, Numerical Recipes, but since I'm new to the field, would you mind pointing me to the appropriate chapter for this kind of problem? Is it the chapter on root finding? –  Herman Oct 14 '10 at 13:28
    
By simple variable substitution I've managed to reduce the formula to the following: $-a(x+k)^k + \sum\limits_{j=0}^{y}x^{j}\bigl(\frac{k}{k-j}\bigr) \leq 0$. This seems right in the domain of root finding, I see. –  Herman Oct 14 '10 at 14:01
    
Sorry, that formula was meant to be: $-a(x+k)^k + \sum\limits_{j=0}^{y}x^{j}\binom{k}{k-j} \leq 0$ –  Herman Oct 14 '10 at 14:08
    
Yes, you have a one-dimensional root finding problem. If you use Stirling for the k choose k-j you can consider the variables to be reals instead of integers. My edition has Brent's method at the bulletproof recommendation and I have used it successfully. –  Ross Millikan Oct 14 '10 at 22:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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