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.

I would like to see if $$ b_l:=4^{-l} \sum_{j=0}^l \frac{\binom{2 l}{2 j} \binom{n}{j}^2}{\binom{2 n}{2 j}}\text{.} $$ is decreasing when $l$ is large enough say around $10^6$. I dont need any theoretical derivations though I wrote the following code part


b=zeros(1,10^7-10^6);

for l=10^6:10^7-1

    for j=0:l

        b(l-999999) = b(l-999999)
            + (nchoosek(2*l,2*j)*nchoosek(10^7,j)^2)
            / (nchoosek(2*10^7,2*j));

    end

end

EDIT:

This question is a simplified version of the original one. I intended to carry the matter here since what I found might imply that the function is no more decreasing for larger $l$. Please see the discussion over there.

Inequality involving sums of fractions of products of binomial coefficients

I couldnt make use of Stirlings approximation. Here is the changed code part:


b=zeros(1,10^7-10^6);

for l=10^6:10^7-1

for j=0:l

    b(l-999999) = b(l-999999)  + ((sqrt(2*pi*2*l)*(2*l/exp(1))^(2*l))/((sqrt(2*pi*2*j)*(2*j/exp(1))^(2*j)*((sqrt(2*pi*2*l)*(2*l/exp(1))^(2*l))-(sqrt(2*pi*2*j)*(2*j/exp(1))^(2*j)))))*... 
                                 ((sqrt(2*pi*10^7)*(10^7/exp(1))^(10^7))/((sqrt(2*pi*j)*(j/exp(1))^(j)*((sqrt(2*pi*10^7)*(10^7/exp(1))^(10^7))-(sqrt(2*pi*j)*(j/exp(1))^(j))))))/...
                                 (sqrt(2*pi*2*10^7)*(2*10^7/exp(1))^(2*10^7))/((sqrt(2*pi*2*j)*(2*j/exp(1))^(2*j)*((sqrt(2*pi*2*10^7)*(2*10^7/exp(1))^(2*10^7))-(sqrt(2*pi*2*j)*(2*j/exp(1))^(2*j))))));

end

end

which cannot provide me any result due to the accuracy of nchoosek, i.e., big numbers are creating problems. Do you have any idea how I can deal with this problem? I only want to know if the function is decreasing or not.

Any help will be appreciated.

Thanks in advance.

share|improve this question
    
It would be only fair to mention, that your question was inspired by an earlier one. –  Sasha Aug 27 '12 at 15:19
    
@Sasha I will edit. Please have a look at the conversations over there. I have some findings on the question and now from there I have another claim. Finally what i do is constructive. I am not interested in answer. I am interested in helping the owner of the original question. –  Seyhmus Güngören Aug 27 '12 at 15:34
add comment

2 Answers

up vote 2 down vote accepted

You can rewrite nchoosek to return the log of nchoosek using Stirling's approximation. It is plenty accurate for your needs.

share|improve this answer
    
what you suggested also didnt help. We have still $\frac{n}{e}^n$ where $n=10^7$. I just modified the code part. –  Seyhmus Güngören Aug 27 '12 at 13:46
    
@SeyhmusGüngören: that is why I suggested taking the log. $\ln n! \approx n \ln n - n + \frac 12 \ln (2 \pi n)$ which is easy to handle. After evaluating the log nchoosek's the big numbers go away with the subtraction and you can exponentiate. –  Ross Millikan Aug 27 '12 at 16:22
    
sorry my mistake. I looked only stirling's appx. Didn't understand that you explicitly mentioned about log-exp. –  Seyhmus Güngören Aug 27 '12 at 16:39
add comment

First hack is to compute using long integers instead of regular integers, doubling the precision.

Also, depending on the value of $n$, an approach could be to transform the fraction. Denote $L=2l, N=2n, J=2j$. Assuming $n \geq l$,

$ \binom{L}{J}/\binom{N}{J} = \frac{L! (N-J)!}{N! (L-J)!} = \frac{L! (N-J)! (N-L)!}{N! (L-J)! (N-L)!} = \frac{(N-J)!}{(L-J)! (N-L)!} / \binom{N}{L} = \binom{N-J}{L-J} / \binom{N}{L} $

and if $l > n$, similar trick would work. Perhaps these would come out better.

Third alternative is to try to cancel the fractions before multiplying, or switch to real numbers and do calculations in floating-point arithmetic, which allows much larger numbers.

share|improve this answer
    
as long as $n!$ exists there is a problem and according to all your proposals we have $n!$. We are talking about $10^7!$ –  Seyhmus Güngören Aug 27 '12 at 13:40
    
@SeyhmusGüngören: No need to compute n!. E.g in floating point arithmetic, computing $\binom{N}{L}$ would require canceling larger of $L!$ or $(N-L)!$ and then compute the quotient by multiplying and dividing in turn, e.g. first from numerator / first from denominator * second (num) / second (den) etc -- no large numbers would be needed at all, except to store the result. –  gt6989b Aug 27 '12 at 14:59
    
I don't agree. The code parts above are working. If you can provide me 100 results for $l$ I can believe. –  Seyhmus Güngören Aug 27 '12 at 16:09
add comment

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.