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?
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?
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");