1
$\begingroup$

I want to find a lower bound of the following

$\sum_{i=0}^{100000}\left|\sum_{j=0}^i (-1)^j \binom{167}{j}\binom{99833}{i-j}\right|.$

Will you kindly give some way?

  • 0
    I want as tight as possible.2012-09-26

1 Answers 1

1

The exact number can be calculated on a computer. The number itself has 29835 decimal digits (which is not intractable to compute on modern computers, but is a bit too large to copy/paste here). It starts with 929 and ending with 720 (so it is between $9.29 \times 10^{29834}$ and $10^{29835}$). It took 1 min 11 seconds to compute on my laptop.

You can compute the number exactly using either my C code or GAP code below.

[Note: The previous version of this post indeed contained a bug -- the command mpz_mul_ui(inc,inc,-1); multiplies by the "unsigned integer" -1 (and therefore gave an incorrect result). We can be more confident in this result, since the C and GAP codes are consistent.]

Here's the (corrected) C code; it uses the GMP library:

#include  #include   int i,j; mpz_t val,inc,inc2;  mpz_t bino_167[168],bino_99833[99834];  int main() {   printf("starting preprocessing stage\n");   // storing the values of (167 choose i) in memory   for(i=0;i<=167;i++) {     mpz_init(bino_167[i]);     mpz_bin_uiui(bino_167[i],167,i);   }    // storing the values of (99833 choose i) in memory   // here I was a bit more efficient by using the identity:   // (x choose i) = (x choose (i-1)) * (x-i+1) / i   mpz_init(bino_99833[0]);   mpz_set_ui(bino_99833[0],1);   for(i=1;i<=99833;i++) {     mpz_init(bino_99833[i]);     mpz_set(bino_99833[i],bino_99833[i-1]);     mpz_mul_ui(bino_99833[i],bino_99833[i],99833-i+1);     mpz_divexact_ui(bino_99833[i],bino_99833[i],i);     if(i%1000==0) printf("computed (99833 choose %d)\n",i);   }   printf("preprocessing stage complete\n");    for(i=0;i<=20;i++) gmp_printf("%d -- %Zd\n",i,bino_99833[i]);    mpz_init(val);   mpz_init(inc);   mpz_init(inc2);   mpz_set_ui(val,0);    for(i=0;i<=167;i++) {     mpz_set_ui(inc2,0);     for(j=0;j<=i;j++) {       // inc = (-1)^j * (167 choose j) * (99833 choose i-j)       mpz_set(inc,bino_167[j]);       mpz_mul(inc,inc,bino_99833[i-j]);       if(j%2==1) mpz_neg(inc,inc);       mpz_add(inc2,inc2,inc);     }     // inc2 = |sum_j inc|     mpz_abs(inc2,inc2);     // val = sum_i inc2     mpz_add(val,val,inc2);   }    for(i=168;i<=100000;i++) {     mpz_set_ui(inc2,0);     for(j=0;j<=167;j++) {       if(i-j>99833) continue; // otherwise bino_99833[i-j] causes seg fault       mpz_set_ui(inc,1);       mpz_mul(inc,inc,bino_167[j]);       mpz_mul(inc,inc,bino_99833[i-j]);       if(j%2==1) mpz_neg(inc,inc);       mpz_add(inc2,inc2,inc);     }     mpz_abs(inc2,inc2);     mpz_add(val,val,inc2);     if(i%1000==0) printf("calculated up to i=%d\n",i);   }    gmp_printf("%d %Zd\n",i,val);    mpz_clear(val);   mpz_clear(inc);   mpz_clear(inc2);   for(i=0;i<=167;i++) mpz_clear(bino_167[i]);   for(i=0;i<=99833;i++) mpz_clear(bino_99833[i]);    return 0; } 

GAP code:

# bino_167[i+1] = (167 choose i) bino_167:=List([0..167],i->Binomial(167,i));;  # bino_99833[i+1] = (99833 choose i) bino_99833:=[1]; for i in [1..99833] do   bino_99833[i+1]:=bino_99833[i]*(99833-i+1)/i; od;  val:=0; for i in [0..100000] do   inc2:=0;   for j in [0..Minimum(167,i)] do     if((i-j)>99833) then continue; fi;     inc:=((-1)^j)*bino_167[j+1]*bino_99833[i-j+1];     inc2:=inc2+inc;   od;   val:=val+AbsInt(inc2); od; Print(val,"\n");