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?

  • 1
    Can you be more specific about the lower bound? I mean.. $0$ is a lower bound but somehow I feel like it is not what you're looking for.. :)2012-09-25
  • 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");