# Lower bound of a series

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?

-
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

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);
}
// inc2 = |sum_j inc|
mpz_abs(inc2,inc2);
// val = sum_i 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_abs(inc2,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");

-