print(`Version of July 25, 1996.`):
lprint(``):
print(`This is SYND`):
print(`A Maple program accompanying the paper`):
print(`"A Cure to Andrews's Syndrome", by S. B. Ekhad, Herb Wilf `):
print(`and Doron Zeilberger, submitted`):
lprint(``):
print(`The most current version of this program is available on WWW at:`):
print(` http://www.math.temple.edu/~zeilberg , where also the paper can be`):
print(`found.`):
lprint(``):
print(`Please report all bugs to: zeilberg@math.temple.edu .`):
print(`All bugs or other comments used will be acknowledged in future`):
print(`versions.`):
lprint(``):
print(`For general help, and a list of the available functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name)" `):
lprint(``):
 
KUKU:=3: 
 
ezra:=proc()
if args=NULL then
print(`ANDREWS_SYNDROME`):
print(`A Maple program for proving Hypergemetric (Binomial Coeff.)`):
print(` identities`):
print(`of the form \sum_k F(n,k,a,b,...)=RHS(n,a,b,..), where`):
print(` a,b,..., are parameters.`):
print(`This program should only be used when procedures zeil or zeilpap`):
print(`of EKHAD runs out of memory, or takes too long.`):
lprint(``):
print(`Contains procedures:PROOF2`):
fi:
 
 
 if nops([args])=1 and op(1,[args])=`PROOF2` then
 
 
  print(`PROOF2(SUMMAND,RHS,k,n,lower_limit,upper_limit,x,z,Certainty)`):
 print(`Proves, (or refutes) Rigorously, identities of the form`):
print(`sum_{k=lower_limit}^{upper_limit} SUMMAND(n,k,params) =RHS(n,params)`):
print(`For a much quicker semi-rigorous proof use SEMIRIGOR`):
lprint(``):
print(`The SUMMAND must be a product of factorials, powers binomials`):
print(`and raising factorials (a)_k denoted by rf(a,k)`):
 
 fi:
 
end:
 
 
yafe:=proc(ope,fu,N)
local fu1,ope2,mekh,mekh1,i,ope1:
ope1:=normal(ope):
fu1:=normal(fu):
mekh:=denom(ope1):
mekh1:=denom(fu1):
ope1:=expand(numer(ope1)):
ope2:=0:
for i from 0 to degree(ope1,N) do
ope2:=ope2+factor(coeff(ope1,N,i))*N^i:
od:
mekh1*ope2,mekh*numer(fu1):
end:
 
 
rf2:=proc(a,b):
 (a+b-1)!/(a-1)!:
end:
 
 
rf1:=proc(a,k)
local gu,i:
if not type(k,integer) or k<0 then
 ERROR(`Second argument must be a positive integer`):
fi:
 
gu:=1:
 
for i from 1 to k do
gu:=gu*(a+i-1):
od:
gu:
end:
 
 
 
RootOf1:=proc(f,x)
local kv,kvi,i:
kv:=[solve(f=0,x)]:
kvi:={}:
for i from 1 to nops(kv) do
 
  if type(kv[i],integer) and kv[i]>0 then
   kvi:=kvi union {kv[i]}
  fi:
 
od:
 
RETURN(kvi):
 
end:
 
pashet:=proc(p,N)
local i,gu1,gu,p1:
p1:=normal(p):
gu1:=denom(p1):
p1:=numer(p1):
p1:=expand(p1):
gu:=0:
for i from 0 to degree(p,N) do
gu:=gu+factor(coeff(p1,N,i))*N^i:
od:
RETURN(gu/gu1):
end:
 
 
 
 
 
 
tryset:=proc(nuparams,Values)
local i,gu,mu,j,mu1:
 
if nuparams<>nops(Values)
then
 ERROR(`both arguments must be of the same length`):
 
fi:
 
if nuparams=1 then
 gu:={}:
 
 for i from 0 to op(1,Values) do
  gu:=gu union {[i]}:
 od:
RETURN(gu):
fi:
 
mu:= tryset(nuparams-1,[op(1..nops(Values)-1,Values) ]):
 
gu:={}:
 
for i from 1 to nops(mu) do
 mu1:=op(i,mu):
 for j from 0 to op(nuparams,Values) do
  gu:=gu union {[op(mu1),j]}:
 od:
od:
 
gu:
end:
 
 
 
 
 
goremd:=proc(N,ORDER)
local i, gu:
gu:=0:
for i from 0 to ORDER do
gu:=gu+(b.i)*N^i:
od:
RETURN(gu):
end:
 
goremc:=proc(D,ORDER)
local i,gu:
gu:=0:
for i from 0 to ORDER do
gu:=gu+(b.i)*D^i:
od:
RETURN(gu):
end:
 
pashetd:=proc(p,N)
local gu,p1,mekh,i:
p1:=normal(p):
mekh:=denom(p1):
p1:=numer(p1):
p1:=expand(p1):
gu:=0:
for i from 0 to degree(p1,N) do
gu:=gu+factor(coeff(p1,N,i))*N^i:
od:
RETURN(gu,mekh):
end:
 
pashetc:=proc(p,D)
local gu,p1,i,mekh:
p1:=normal(p):
mekh:=denom(p1):
p1:=numer(p1):
p1:=expand(p1):
gu:=0:
for i from 0 to degree(p1,D) do
gu:=gu+factor(coeff(p1,D,i))*D^i:
od:
RETURN(gu,mekh):
end:
 
 
 
 
bdokct:=proc(SUMMAND1,ORDER,k,n,N)
local mu,gu,i,G1,ope,lu,SUMMAND:
 
SUMMAND:=convert(SUMMAND1,factorial):
mu:=ct(SUMMAND,ORDER,k,n,N):
 
if mu=0 then
 RETURN(0):
fi:
 
ope:=mu[1]:
G1:=mu[2]*SUMMAND:
gu:=0:
 
for i from 0 to degree(ope,N) do
gu:=gu+coeff(ope,N,i)*simplify1(SUMMAND,n,i):
gu:=normal(gu):
od:
 
lu:=subs(k=k+1,mu[2])*simplify1(SUMMAND,k,1)-mu[2]:
lu:=normal(lu):
normal(gu/lu);
end:
 
 
 
 
with(linalg):
degdet:=proc(resh,x)
local n,i,j,mat:
 
n:=nops(resh):
mat:=matrix(n,n):
 
for i from 1 to n do
 for j from 1 to n do
  mat[i,j]:=x^degree(op(j,op(i,resh)),x):
 od:
od:
 
degree(permanent(mat),x):
 
end:
 
 
 
ctpar2:=proc(SUMMAND,ORDER,k,n,N,x,z,Certainty)
local muk,kuz1,gu,i,ope,POL1,SUMMAND1,yakhas,P,Q,R,res1,hakhi,g,
A1, B1,  P1,A1t,B1t,
degg, eq, fu, gugu, i1, ia1, k1,  l1, l2, meka1, mekb1, mumu, eqsp,
va1, va2,denFAC,SUMMANDspec,kuz,Degresh,
herb,ix,iz,in1:
 
if Certainty<=0 or Certainty >1 then
 ERROR(`The last argument must be between 0 and 1`):
fi:
 
if nargs<>8 then
ERROR(`ctpar2(F,ORDER,summation_variable,auxiliary_var,N,x,z,Certainty)`):
fi:
 
 
 
SUMMANDspec:=subs(x=1/3 ,SUMMAND):
print(`When`, x=1/3):
 
 
SUMMANDspec:=subs(z=1/5 ,SUMMANDspec):
print(`and When`, z=1/5):
 
 
herb:=ct(SUMMANDspec,ORDER,k,n,N):
if  herb=0 then
 RETURN(0):
fi:
 
print(`the operator ope(N,n) is`):
print( herb[1]):
 
 
 
SUMMANDspec:=subs(x=-1/4 ,SUMMAND):
print(`When`, x=-1/4):
 
 
SUMMANDspec:=subs(z=1/7 ,SUMMANDspec):
print(`and When`, z=1/7):
 
 
herb:=ct(SUMMANDspec,ORDER,k,n,N):
if  herb=0 then
 RETURN(0):
fi:
 
print(`the operator ope(N,n) is`):
print( herb[1]):
 
 
 
ope:=0:
 
for i from 0 to ORDER do
 ope:=ope+b.i*N^i:
od:
 
 
gu:=hafel(1,convert(SUMMAND,factorial),ope,n,N):
 
POL1:=gu[1]:
SUMMAND1:=gu[2]:
denFAC:=gu[3]:
yakhas:=simplify1(SUMMAND1,k,-1):
yakhas:=normal(1/yakhas):
 
 
P1:=1:
Q:=numer(yakhas):
R:=denom(yakhas):
 
res1:=findgQR(Q,R,k,100):
 
while res1[2]<>0 do
 g:=res1[1]:
 hakhi:=res1[2]:
 Q:=normal(Q/g):
 R:=normal(R/subs(k=k-hakhi,g)):
 P1:=P1*product(subs(k=k-i1,g),i1=0..hakhi-1):
 res1:=findgQR(Q,R,k,100):
od:
 
P:=POL1*P1:
 
A1:=subs(k=k+1,Q)+R:
A1t:=A1:
 
 
 A1t:=subs({x=1/6,z=1/7},A1t):
 
 
A1t:=expand(A1t):
B1:=subs(k=k+1,Q)-R:
 
B1t:=B1:
B1t:=subs({x=1/6,z=1/7},B1t):
 
B1t:=expand(B1t):
 
l1:=degree(A1t,k):
if B1=0 then
l2:=-100:
else
l2:=degree(B1t,k):
fi:
meka1:=coeff(A1t,k,l1):
mekb1:=coeff(B1t,k,l2):
if l1<=l2 
then
k1:=degree(P,k)-l2:
elif l2=l1-1 
then
 mumu:= (-2)*normal(mekb1/meka1):
  if type(mumu,integer) 
  then
   k1:=max(mumu, degree(P,k)-l1+1):
  else
   k1:=degree(P,k)-l1+1:
  fi:
elif l2 < l1-1
then
 k1:= max( 0, degree(P,k)-l1+1 ):
fi:
fu:=0:
 
if k1 < 0 then
print(k1):
RETURN(0):
fi:
 
 
for ia1 from 0 to k1 do
fu:=fu+a.ia1*k^ia1:
od:
gugu:=subs(k=k+1,Q)*fu-R*subs(k=k-1,fu)-P:
degg:=degree(gugu,k):
gugu:=taylor(gugu,k=0,degg+2):
 
for ia1 from 0 to degg do
eq[ia1+1]:=coeff(gugu,k,ia1)=0:
od:
for ia1 from 0 to k1 do
va1[ia1+1]:=a.ia1:
od:
for ia1 from 0 to ORDER do
va2[ia1+1]:=b.ia1
od:
eq:=convert(eq,set):
eq:=eq minus {0=0}:
va1:=convert(va1,set):
va2:=convert(va2,set):
va1:=va1 union va2:
 
print(`Let F(n,k):=`):
print(SUMMAND):
lprint(``):
print(`We will prove that its sum w.r.t. k is identically 0.`):
lprint(``):
lprint(`We already know this for`, n,`=0..`, max(0,ORDER-1)):
lprint(``):
print(`We claim that there exists a linear recurrence operator, `):
print(`ope(N,n):=`,ope,`,`):
print(`with coefficients that are polynomials of`,x,z):
print(`and a polynomial in`,n,`and the variables`, n,x,z):
print(`POLY:=`,fu):
print(`such that G(n,k):=`):
print(subs(k=k+1,Q)*fu/P1/denFAC ):
print(`satisfies`):
print(`ope(N,n)F(n,k)=G(n,k+1)-G(n,k).`):
lprint(``):
print(`It would then follow that  the sum, a(n), of F(n,k) w.r.t. to k`):
print(`is annihilated by ope(N,n), and all we would have to check is`):
print(`that the coefficient of`,N^ORDER,` in ope(N,n) does not  `):
print(`have positive integer roots.`):
print(`This will become apparent when we print out the ope(N,n)`):
lprint(`for specific values of the parameters:`,x,z,`.`):
lprint(``):
print(`Any factor of the form (n-positive integer) in ope(N,n)`):
print(`would also show up in any specialization of the parameters.`):
 
lprint(``):
lprint(`Indeed, the coefficients of both ope(N,n) and POLY, defined above`):
print(`are solutions of a certain set of homogenous equations`):
#lprint(eq):
lprint(``):
print(`in the set of variables`):
print(va1):
lprint(``):
print(`To prove that ope(N,n) and POLY exist, we must prove that`):
print(`this system of homogeneous equations has a non-trivial  solution.`):
 
kuz:=lemat(eq,convert(va1,list)):
print(`In terms of the list of variables`):
print(convert(va1,list)):
lprint(``):
 
print(`we have to prove that the matrix of coeffs., let's call it M `):
#lprint(kuz):
print(`times the vector of variables`):
lprint(convert(va1,list)):
print(`has a non-trivial solution.`):
 
if nops(kuz)=nops(va1) then
print(`Since the number of eqations equals the number of unknowns,`):
print(`this means that we have to show that its determinant vanishes.`):
elif nops(kuz)<nops(va1) then
 print(`Since the number of equations is less than the number of vars`):
 print(`there must be a solution`):
 RETURN(`OK`):
else
 print(`We have more equations than unknown, so let's take the top`):
 print(nops(op(1,kuz)),`rows of the matrix`):
 kuz:=[op(1..nops(op(1,kuz)),kuz)]:
fi:
 
 
Degresh:=[degdet(kuz, x), degdet(kuz, z),degdet(kuz,n)]:
 
 
print(`By looking at the coefficients of the entries, it is immediately`):
print(`seen that the determinant is a poly. whose degrees are at  most,`):
 
lprint(`in`, x ,`is`,op(1,Degresh)):
lprint(`in`, z ,`is`,op(2,Degresh)):
lprint(`in`, n ,`is`,op(3,Degresh)):
 
 
lprint(``):
print(`In order to prove the existence of ope(N,n) and POLY mentioned`):
print(`above with certainty`, Certainty):
print(`we will check that the matrix is singular by pluging in`):
print(`enough special values for the parameters:`):
print(`and compute its determinant there, to make sure that it is always`):
print(`zero. Since a polynomial of degree k in a variable x is identically`):
print(`zero if it vanishes at k+1 distinct values, it is enough to check`):
print(`that our determinant vanishes, when`):
print(x,`is in the range`):
print([-trunc(op(1,Degresh)/2),trunc(op(1,Degresh)/2)]):
print(z,`is in the range`):
print([-trunc(op(2,Degresh)/2),trunc(op(2,Degresh)/2)]):
print(n,`is in the range`):
print([-trunc(op(3,Degresh)/2),trunc(op(3,Degresh)/2)]):
 
if Certainty<1 then
 print(`Since you are willing to settle for a semirigorous proof`):
 print(`We will chop the above interval by`,Certainty):
fi:
 
 
 
muk:=0:
for ix from  -trunc(Certainty*op(1,Degresh)/2) to 
     trunc(Certainty*op(1,Degresh)/2) do
 
 
for iz from  -trunc(Certainty*op(2,Degresh)/2) to 
     trunc(Certainty*op(2,Degresh)/2) do
 
for in1 from  -trunc(Certainty*op(3,Degresh)/2) to 
     trunc(Certainty*op(3,Degresh)/2) do
 
muk:=muk+1:
kuz1:=subs({x=ix,z=iz,n=in1},kuz):
kuz1:=convert(kuz1,matrix):
if det(kuz1)<>0 then
print(`When`, x=ix,`and when`,z=iz,`and when`,n=in1):
print(`The determinant is `,det(kuz1)):
RETURN(`Wrong`):
fi:
if type(muk/100,integer) then
 print(`So far the det. was proved 0 for `,muk,`special cases`):
fi:
od:od:od:
print(`We have just performed this task, hence`):
print(`The identity was proved with certainty`,Certainty):
 
end:
 
 
ctpar1:=proc(SUMMAND,ORDER,k,n,N,x,Certainty)
local muk,kuz1,gu,i,ope,POL1,SUMMAND1,yakhas,P,Q,R,res1,hakhi,g,
A1, B1,  P1,A1t,B1t,
degg, eq, fu, gugu, i1, ia1, k1,  l1, l2, meka1, mekb1, mumu, 
va1, va2,denFAC,SUMMANDspec,kuz,Degresh,
herb,ix,in1:
 
if Certainty<=0 or Certainty >1 then
 ERROR(`The last argument must be between 0 and 1`):
fi:
 
if nargs<>7 then
ERROR(`ctpar1(F,ORDER,summation_variable,auxiliary_var,N,x,Certainty)`):
fi:
 
 
 
SUMMANDspec:=subs(x=1/3 ,SUMMAND):
print(`When`, x=1/3):
 
 
herb:=ct(SUMMANDspec,ORDER,k,n,N):
if  herb=0 then
 RETURN(0):
fi:
 
print(`the operator ope(N,n) is`):
print( herb[1]):
 
 
 
SUMMANDspec:=subs(x=-1/4 ,SUMMAND):
print(`When`, x=-1/4):
 
herb:=ct(SUMMANDspec,ORDER,k,n,N):
if  herb=0 then
 RETURN(0):
fi:
 
print(`the operator ope(N,n) is`):
print( herb[1]):
 
 
 
ope:=0:
 
for i from 0 to ORDER do
 ope:=ope+b.i*N^i:
od:
 
 
gu:=hafel(1,convert(SUMMAND,factorial),ope,n,N):
 
POL1:=gu[1]:
SUMMAND1:=gu[2]:
denFAC:=gu[3]:
yakhas:=simplify1(SUMMAND1,k,-1):
yakhas:=normal(1/yakhas):
 
 
P1:=1:
Q:=numer(yakhas):
R:=denom(yakhas):
 
res1:=findgQR(Q,R,k,100):
 
while res1[2]<>0 do
 g:=res1[1]:
 hakhi:=res1[2]:
 Q:=normal(Q/g):
 R:=normal(R/subs(k=k-hakhi,g)):
 P1:=P1*product(subs(k=k-i1,g),i1=0..hakhi-1):
 res1:=findgQR(Q,R,k,100):
od:
 
P:=POL1*P1:
 
A1:=subs(k=k+1,Q)+R:
A1t:=A1:
 
 
 A1t:=subs({x=1/6},A1t):
 
 
A1t:=expand(A1t):
B1:=subs(k=k+1,Q)-R:
 
B1t:=B1:
B1t:=subs({x=1/6},B1t):
 
B1t:=expand(B1t):
 
l1:=degree(A1t,k):
if B1=0 then
l2:=-100:
else
l2:=degree(B1t,k):
fi:
meka1:=coeff(A1t,k,l1):
mekb1:=coeff(B1t,k,l2):
if l1<=l2 
then
k1:=degree(P,k)-l2:
elif l2=l1-1 
then
 mumu:= (-2)*normal(mekb1/meka1):
  if type(mmu,integer) 
  then
   k1:=max(mumu, degree(P,k)-l1+1):
  else
   k1:=degree(P,k)-l1+1:
  fi:
elif l2 < l1-1
then
 k1:= max( 0, degree(P,k)-l1+1 ):
fi:
fu:=0:
 
if k1 < 0 then
print(k1):
RETURN(0):
fi:
 
 
for ia1 from 0 to k1 do
fu:=fu+a.ia1*k^ia1:
od:
gugu:=subs(k=k+1,Q)*fu-R*subs(k=k-1,fu)-P:
degg:=degree(gugu,k):
gugu:=taylor(gugu,k=0,degg+2):
 
for ia1 from 0 to degg do
eq[ia1+1]:=coeff(gugu,k,ia1)=0:
od:
for ia1 from 0 to k1 do
va1[ia1+1]:=a.ia1:
od:
for ia1 from 0 to ORDER do
va2[ia1+1]:=b.ia1
od:
eq:=convert(eq,set):
eq:=eq minus {0=0}:
va1:=convert(va1,set):
va2:=convert(va2,set):
va1:=va1 union va2:
 
print(`Let F(n,k):=`):
print(SUMMAND):
lprint(``):
print(`We will prove that its sum w.r.t. k is identically 0.`):
lprint(``):
lprint(`We already know this for`, n,`=0..`, max(0,ORDER-1)):
lprint(``):
print(`We claim that there exists a linear recurrence operator, `):
print(`ope(N,n):=`,ope,`,`):
print(`with coefficients that are polynomials of`,x):
print(`and a polynomial in`,n,`and the variables`,n, x):
print(`POLY:=`,fu):
print(`such that G(n,k):=`):
print(subs(k=k+1,Q)*fu/P1/denFAC ):
print(`satisfies`):
print(`ope(N,n)F(n,k)=G(n,k+1)-G(n,k).`):
lprint(``):
print(`It would then follow that  the sum, a(n), of F(n,k) w.r.t. to k`):
print(`is annihilated by ope(N,n), and all we would have to check is`):
print(`that the coefficient of`,N^ORDER,` in ope(N,n) does not  `):
print(`have positive integer roots.`):
print(`This will become apparent when we print out the ope(N,n)`):
lprint(`for specific values of the parameters:`,x,`.`):
lprint(``):
print(`Any factor of the form (n-positive integer) in ope(N,n)`):
print(`would also show up in any specialization of the parameters.`):
 
lprint(``):
lprint(`Indeed, the coefficients of both ope(N,n) and POLY, defined above`):
print(`are solutions of a certain set of homogenous equations`):
#lprint(eq):
lprint(``):
print(`in the set of variables`):
print(va1):
lprint(``):
print(`To prove that ope(N,n) and POLY exist, we must prove that`):
print(`this system of homogeneous equations has a non-trivial  solution.`):
 
kuz:=lemat(eq,convert(va1,list)):
print(`In terms of the list of variables`):
print(convert(va1,list)):
lprint(``):
 
print(`we have to prove that the matrix of coeffs., let's call it M `):
lprint(kuz):
print(`times the vector of variables`):
lprint(convert(va1,list)):
print(`has a non-trivial solution.`):
 
if nops(kuz)=nops(va1) then
print(`Since the number of equations equals the number of unknowns,`):
print(`this means that we have to show that its determinant vanishes.`):
elif nops(kuz)<nops(va1) then
 print(`Since the number of equations is less than the number of vars`):
 print(`there must be a solution`):
 RETURN(`OK`):
else
 print(`We have more equations than unknown, so let's take the top`):
 print(nops(op(1,kuz)),`rows of the matrix`):
 kuz:=[op(1..nops(va1),kuz)]:
fi:
 
 
Degresh:=[degdet(kuz, x),degdet(kuz,n)]:
 
 
print(`By looking at the coefficients of the entries, it is immediately`):
print(`seen that the determinant is a poly. whose degrees are at  most,`):
 
lprint(`in`, x ,`is`,op(1,Degresh)):
lprint(`in`, n ,`is`,op(2,Degresh)):
 
 
lprint(``):
print(`In order to prove the existence of ope(N,n) and POLY mentioned`):
print(`above with certainty`, Certainty):
print(`we will check that the matrix is singular by pluging in`):
print(`enough special values for the parameters:`):
print(`and compute its determinant there, to make sure that it is always`):
print(`zero. Since a polynomial of degree k in a variable x is identically`):
print(`zero if it vanishes at k+1 distinct values, it is enough to check`):
print(`that our determinant vanishes, when`):
print(x,`is in the range`):
print([-trunc(op(1,Degresh)/2),trunc(op(1,Degresh)/2)]):
print(n,`is in the range`):
print([-trunc(op(2,Degresh)/2),trunc(op(2,Degresh)/2)]):
if Certainty<1 then
 print(`Since you are willing to settle for a semirigorous proof`):
 print(`We will chop the above intervals by`,Certainty):
fi:
 
 
muk:=0:
for ix from  -trunc(Certainty*op(1,Degresh)/2) to 
     trunc(Certainty*op(1,Degresh)/2) do
 
 
for in1 from  -trunc(Certainty*op(2,Degresh)/2) to 
     trunc(Certainty*op(2,Degresh)/2) do
 
muk:=muk+1:
kuz1:=subs({x=ix,n=in1},kuz):
kuz1:=convert(kuz1,matrix):
if det(kuz1)<>0 then
print(`When`, x=ix,`and when`,n=in1):
print(`The determinant is `,det(kuz1)):
RETURN(`Wrong`):
fi:
if type(muk/100,integer) then
 print(`So far the det. was proved 0 for `,muk,`special cases`):
fi:
od:od:
print(`We have just performed this task, hence`):
print(`The identity was proved with certainty`,Certainty):
 
end:
 
 
ct:=proc(SUMMAND,ORDER,k,n,N)
local gu,i,ope,POL1,SUMMAND1,yakhas,P,Q,R,j,res1,hakhi,g,
A1, B1,  P1, SDZ, SDZ1,
degg, eq, fu, gugu, i1, ia1, k1, kvutsa, l1, l2, meka1, mekb1, mumu, 
va1, va2,ope1,denFAC,ope1a:
 
if nargs<>5 then
ERROR(`Syntax: ct(SUMMAND,ORDER,summation_variable,auxiliary_var, Shift_n)`):
fi:
 
 
ope:=0:
 
for i from 0 to ORDER do
 ope:=ope+b.i*N^i:
od:
 
gu:=hafel(1,convert(SUMMAND,factorial),ope,n,N):
POL1:=gu[1]:
SUMMAND1:=gu[2]:
denFAC:=gu[3]:
yakhas:=simplify1(SUMMAND1,k,-1):
yakhas:=normal(1/yakhas):
 
P1:=1:
Q:=numer(yakhas):
R:=denom(yakhas):
 
 
res1:=findgQR(Q,R,k,100):
 
while res1[2]<>0 do
 g:=res1[1]:
 hakhi:=res1[2]:
 Q:=normal(Q/g):
 R:=normal(R/subs(k=k-hakhi,g)):
 P1:=P1*product(subs(k=k-i1,g),i1=0..hakhi-1):
 res1:=findgQR(Q,R,k,100):
od:
 
P:=POL1*P1:
 
A1:=subs(k=k+1,Q)+R:
A1:=expand(A1):
B1:=subs(k=k+1,Q)-R:
B1:=expand(B1):
l1:=degree(A1,k):
if B1=0 then
l2:=-100:
else
l2:=degree(B1,k):
fi:
meka1:=coeff(A1,k,l1):
mekb1:=coeff(B1,k,l2):
if l1<=l2 
then
k1:=degree(P,k)-l2:
elif l2=l1-1 
then
 mumu:= (-2)*mekb1/meka1:
  if type(mumu,integer) 
  then
   k1:=max(mumu, degree(P,k)-l1+1):
  else
   k1:=degree(P,k)-l1+1:
  fi:
elif l2 < l1-1
then
 k1:= max( 0, degree(P,k)-l1+1 ):
fi:
fu:=0:
 
 
if k1 < 0 then
RETURN(0):
fi:
if k1 >= 0 then
for ia1 from 0 to k1 do
fu:=fu+a.ia1*k^ia1:
od:
gugu:=subs(k=k+1,Q)*fu-R*subs(k=k-1,fu)-P:
gugu:=expand(gugu):
degg:=degree(gugu,k):
 
for ia1 from 0 to degg do
eq[ia1+1]:=coeff(gugu,k,ia1)=0:
od:
for ia1 from 0 to k1 do
va1[ia1+1]:=a.ia1:
od:
for ia1 from 0 to ORDER do
va2[ia1+1]:=b.ia1
od:
eq:=convert(eq,set):
va1:=convert(va1,set):
va2:=convert(va2,set):
va1:=va1 union va2:
va1:=solve(eq,va1):
kvutsa:={va1}:
fu:=subs(va1,fu):
ope:=subs(va1,ope):
fi:
 
 
 
if ope=0 or kvutsa={} or fu=0 then
RETURN(0):
fi:
gu:={}:
for i1 from 0 to k1 do
gu:=gu union {a.i1=1}:
od:
for i1 from 0 to ORDER do
gu:=gu union {b.i1=1}:
od:
fu:=subs(gu,fu):
ope:=subs(gu,ope):
 
ope:=pashet(ope,N):
ope1:=ope*denom(ope):
 
SDZ:=denom(ope)*subs(k=k+1,Q)*fu/P1/denFAC :
SDZ1:=subs(k=k-1,SDZ)*simplify1(convert(SUMMAND,factorial),k,-1):
SDZ1:=simplify(SDZ1):
 
ope1a:=0:
for i from 0 to degree(ope1,N) do
ope1a:=ope1a+sort(coeff(ope1,N,i)*N^i):
od:
 
RETURN(ope1a,SDZ1):
end:
 
 
 
 
 
findgQR:=proc(Q,R,k,L)
local j,g:
 
for j from 1 to L do
 g:=gcd(Q,subs(k=k+j,R)):
 if degree(g,k)>0 then
  RETURN(g,j):
 fi:
od:
1,0:
end:
 
 
 
hafel:=proc(POL,SUMMAND,ope,n,N)
local i,FAC,degg,bi,rat,POL1,SUMMAND1,zub:
degg:=degree(ope,N):
FAC:=0:
 
for i from 0 to degg do
 bi:=coeff(ope,N,i):
 rat:=simplify1(SUMMAND,n,i):
 FAC:=FAC+bi*subs(n=n+i,POL)*rat:
 FAC:=normal(FAC):
od:
 
POL1:=numer(FAC):
zub:=denom(FAC):
SUMMAND1:=SUMMAND/zub:
RETURN(POL1,SUMMAND1,zub):
end:
 
  
simplify1:=proc(bitu,k,a)
local gu,gu1,i,khez,sp:
sp:=1:
gu:=bitu:
 
if type(gu,`*`) then
 
 for i from 1 to nops(gu) do
  gu1:=op(i,gu):
 
 if type(gu1,`^`) and type(op(2,gu1), integer) then
 
     khez:=op(2,gu1):
     gu1:=op(1,gu1):
     sp:=sp*simplify(subs(k=k+a,gu1)/gu1)^khez:
  
   else 
     sp:=sp*simplify(subs(k=k+a,gu1)/gu1):
 
   fi:
 
od:
 
elif type(gu,`^`) and type(op(2,gu), integer) then
   khez:=op(2,gu):
   gu1:=op(1,gu):
   sp:=sp*simplify(subs(k=k+a,gu1)/gu1)^khez:  
 
 
else
 
 sp:=simplify(subs(k=k+a,gu)/gu):
 
fi:
 
sp:
 
end:
 
 
with(linalg):
lemat:=proc(eq,var)
local ku,kaz,i,mat,eq1,j,i9:
 
eq1:={}:
 
for i from 1 to nops(eq) do
if not (op(1,op(i,eq))=0 and op(2,op(i,eq))=0)
then
 eq1:=eq1 union {op(i,eq)}:
fi:
if op(2,op(i,eq))<>0 then
ERROR(`Not homogenous`):
fi:
od:
 
mat:=[]:
 
for i from 1 to nops(eq1) do
kaz:=[]:
 for j from 1 to nops(var) do
   ku:=op(1,op(i,eq1)):
    ku:=taylor(ku,op(j,var)=0,2):
    kaz:=[op(kaz),coeff(ku,op(j,var),1)]:
 od:
if kaz<>[seq(0,i9=1..nops(kaz))] then
mat:=[op(mat),kaz]:
fi:
od:
 
mat:
end:
 
Wize:=proc(H,n)
local RAT:
RAT:=simplify1(convert(H,factorial),n,1)-1:
RAT:=normal(RAT):
RAT*convert(H,factorial):
end:
 
 
 
 
 
findgQR:=proc(Q,R,k,L)
local j,g:
 
 
for j from 1 to L do
 g:=gcd(Q,subs(k=k+j,R)):
 if degree(g,k)>0 then
  RETURN(g,j):
 fi:
od:
1,0:
end:
 
  
 
  
PROOF2:=proc(SUMMAND1,RHS,k,n,lower_limit,upper_limit,x,z,Certainty)
local lu,N,gu,k1,n1,SUMMAND,SUsp,ORDER,ORDER1,kapip:
 
print(`Rigorous Proof of A Summation Identity Involving Auxiliary Parameters`)
:
lprint(``):
print(`By Shalosh B. Ekhad (E-mail: ekhad@math.temple.edu)`):
lprint(``):
 
 
lprint(`Let F(`,n,`,`,k,`):=`):
print(SUMMAND1):
lprint(``):
print(`Theorem:`):
lprint(``):
print(Sum(F(n,k),k=lower_limit..upper_limit)=RHS):
lprint(``):
lprint(`Proof:`):
lprint(`I will  first check it for the first`,KUKU+1,` values of`,n):
for n1 from 0 to KUKU do
 
 
lu:=0:
for k1 from subs(n=n1,lower_limit) to subs(n=n1,upper_limit) do
lu:=lu+subs({k=k1,n=n1},subs(rf=rf1,SUMMAND1)):
od:
lu:=convert(lu,factorial):
lu:=lu/subs(n=n1,subs(rf=rf1,RHS)):
lu:=expand(lu):
lu:=simplify(lu):
lu:=expand(lu):
lu:=normal(lu):
 
if lu=1 then
 print(`The identity is true when n=`,n1):
else
 print(factor(lu)):
 print(`Theorem fails at`,n=n1):
 kapip:=0:
fi:
od:
 
if kapip=0 then
 ERROR(`Identity is wrong as stated`):
fi:
 
print(`We now know that the identity holds for`,n=0..KUKU):
lprint(``):
lprint(`Let's divide by the right side, making it 1, and let's call`):
lprint(`the new summand also F(n,k).`):
lprint(`The identity is equivalent to`):
lprint(``):
 
print(`Theorem':`):
lprint(`Let F(`,n,`,`,k,`):=`):
print(SUMMAND1/RHS):
lprint(``):
lprint(``):
print(`Then`,Sum(F(n,k),k=lower_limit..upper_limit)=1,`.`):
lprint(``):
lprint(`But this is clearly equivalent to, (since the identity is true`):
lprint(` at`, n,`=0)`,`,`,`to the following`):
lprint(``):
print(Sum(F(n+1,k)-F(n,k),k=lower_limit..upper_limit)=0,`(*)`):
lprint(``):
SUMMAND:=convert(eval(subs(rf=rf2,SUMMAND1)),factorial);
SUMMAND:=SUMMAND/convert(eval(subs(rf=rf2,RHS)),factorial):
SUMMAND:=normal(SUMMAND):
 
 
SUMMAND:=Wize(SUMMAND,n):
 
lprint(` Hence  it suffices to prove:`):
lprint(``):
print(Sum(SUMMAND,k=lower_limit..upper_limit)=0,`(*)`):
lprint(``):
 
SUsp:=SUMMAND:
 
 
SUsp:=subs({x=1/3,z=1/5},SUsp):
 
gu:=0:
 
for ORDER from 0 while  gu=0 do
gu:=ct(SUsp,ORDER,k,n,N):
od:
ORDER:=degree(gu[1],N):
 
 
SUsp:=subs({x=-1/3,z=1/7},SUMMAND):
 
gu:=0:
 
for ORDER1 from 0 while  gu=0 do
gu:=ct(SUsp,ORDER1,k,n,N):
od:
ORDER1:=degree(gu[1],N):
 
 
 if ORDER<>ORDER1 then
ERROR(`Something a little fishy`):
fi:
 
ORDER:=max(ORDER,ORDER1):
 
ctpar2(SUMMAND,ORDER,k,n,N,x,z,Certainty):
end:
 
 
  
PROOF1:=proc(SUMMAND1,RHS,k,n,lower_limit,upper_limit,x,Certainty)
local lu,N,gu,k1,n1,SUMMAND,SUsp,ORDER,ORDER1:
 
print(`Rigorous Proof of A Summation Identity Involving Auxiliary Parameters`)
:
lprint(``):
print(`By Shalosh B. Ekhad (E-mail: ekhad@math.temple.edu)`):
lprint(``):
 
 
lprint(`Let F(`,n,`,`,k,`):=`):
print(SUMMAND1):
lprint(``):
print(`Theorem:`):
lprint(``):
print(Sum(F(n,k),k=lower_limit..upper_limit)=RHS):
lprint(``):
lprint(`Proof:`):
lprint(`I will  first check it for the first`,KUKU+1,` values of`,n):
for n1 from 0 to KUKU do
 
 
lu:=0:
for k1 from subs(n=n1,lower_limit) to subs(n=n1,upper_limit) do
lu:=lu+subs({k=k1,n=n1},subs(rf=rf1,SUMMAND1)):
od:
lu:=convert(lu,factorial):
lu:=lu/subs(n=n1,subs(rf=rf1,RHS)):
lu:=expand(lu):
lu:=simplify(lu):
lu:=expand(lu):
lu:=normal(lu):
 
if lu=1 then
 print(`The identity is true when n=`,n1):
else
 ERROR(`Theorem fails at`,n=n1):
fi:
od:
 
print(`We now know that the identity holds for`,n=0..KUKU):
lprint(``):
lprint(`Let's divide by the right side, making it 1, and let's call`):
lprint(`the new summand also F(n,k).`):
lprint(`The identity is equivalent to`):
lprint(``):
 
print(`Theorem':`):
lprint(`Let F(`,n,`,`,k,`):=`):
print(SUMMAND1/RHS):
lprint(``):
lprint(``):
print(`Then`,Sum(F(n,k),k=lower_limit..upper_limit)=1,`.`):
lprint(``):
lprint(`But this is clearly equivalent to, (since the identity is true`):
lprint(` at`, n,`=0)`,`,`,`to the following`):
lprint(``):
print(Sum(F(n+1,k)-F(n,k),k=lower_limit..upper_limit)=0,`(*)`):
lprint(``):
SUMMAND:=convert(eval(subs(rf=rf2,SUMMAND1)),factorial);
SUMMAND:=SUMMAND/convert(eval(subs(rf=rf2,RHS)),factorial):
SUMMAND:=normal(SUMMAND):
 
 
SUMMAND:=Wize(SUMMAND,n):
 
lprint(` Hence  it suffices to prove:`):
lprint(``):
print(Sum(SUMMAND,k=lower_limit..upper_limit)=0,`(*)`):
lprint(``):
 
SUsp:=SUMMAND:
 
 
SUsp:=subs({x=1/3},SUsp):
 
gu:=0:
 
for ORDER from 0 while  gu=0 do
gu:=ct(SUsp,ORDER,k,n,N):
od:
ORDER:=degree(gu[1],N):
 
 
SUsp:=subs({x=-1/3},SUMMAND):
 
gu:=0:
 
for ORDER1 from 0 while  gu=0 do
gu:=ct(SUsp,ORDER1,k,n,N):
od:
ORDER1:=degree(gu[1],N):
 
 
 if ORDER<>ORDER1 then
ERROR(`Something a little fishy`):
fi:
 
ORDER:=max(ORDER,ORDER1):
 
ctpar1(SUMMAND,ORDER,k,n,N,x,Certainty):
end: