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 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?

share|improve this question
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.. :) –  uforoboa Sep 25 '12 at 16:51
    
I want as tight as possible. –  user12290 Sep 26 '12 at 4:26

1 Answer 1

up vote 1 down vote accepted

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 <stdio.h>
#include <gmp.h>

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");
share|improve this answer

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.