#John Kim
#Use whatever you like

Help:=proc(): print(` Di(L) , NGF(L,x) , SumPol(P,n), F(a,b), G(a,b), VerifyG(), Gk(k,a,b), VerifyGk(), Gk1k2(k1,k2,a,b), F3(a,b,c), G3(a,b,c)`): 
print(`F(a,b) ,G(a,b) `):
end:

Di:=proc(L) local i:
[ seq( L[i+1]-L[i],i=1..nops(L)-1)]:
end:

#NGF(L,x): The unique polynomial P(x)
#expressed in terms of binomial(x,k)
#such that P(i)=L[i+1] for i from 0 to nops(L)-1

NGF:=proc(L,x) local i,L1,P:

L1:=L:

P:=0:
for i from 1 to nops(L) do
 
  P:=P+L1[1]*binomial(x,i-1):

  L1:=Di(L1):

 
  if convert(L1,set)={0} then
    RETURN(factor(expand(P))):
  fi:

od:

factor(expand(P)):

end:

#SumPol(P,n): an empirical yet rigorous algorithm that
#inputs a polynomial expression P, of n, and outputs
#the polynomial expression for the indefinite sum
#add(P(i),i=0..n):

SumPol:=proc(P,n) local d, L,i,j,Q:


d:=degree(P,n):

L:=[ seq(eval(P,n=i), i=0..d+1)]:

Q:=factor(NGF([seq(add(L[j],j=1..i), i=1..nops(L))],n)):

#Is Q(n)-Q(n-1)=P(n)

 if expand(Q-subs(n=n-1,Q)-P) <>0 then
   print(`WE ARE STUPID!, SHAME ON US!`):
   RETURN(FAIL):
  fi:

Q:

end:

#F(a,b): the number of walks from [0,0] to [a,b]
#using positive unit steps ([1,0], [0,1])
F:=proc(a,b) option remember:

if a=0 or b=0 then
   1:
else
  F(a-1,b)+F(a,b-1):
fi:

end:

#G(a,b): the number of walks from [0,0] to [a,b]
#using positive unit steps ([1,0], [0,1]) always
#staying in the safe region a>=b
G:=proc(a,b) option remember:

if b=0 then
   1:
elif b>a then
  0:

else
  G(a-1,b)+G(a,b-1):
fi:

end:


#CONJECTURE: G(a,b) = (a+b)(a+b-1)*...*(a+2)*(a-(b-1))/b! for a>=b
#VerifyG(): Proves conjecture is true by verifying that H=RHS satisfies recurrence relations and initial conditions of G.
VerifyG:=proc() local H,x,y,i1,i2,i3:

H:=(a,b)->product(a+b-i,i=0..b-2)*(a-(b-1))/b!:

i1:=simplify(H(x,x)-H(x,x-1)):
i2:=simplify(H(x-1,y)+H(x,y-1)-H(x,y)):
i3:=simplify(H(x,0)-1):

evalb({i1,i2,i3} = {0}):
end:



#Gk(k,a,b): the number of walks from [0,0] to [a,b]
#using positive unit steps ([1,0], [0,1]) always
#staying in the safe region a>=b-k
Gk:=proc(k,a,b) option remember:

if b>a+k then
  0:
elif a=0 or b=0 then
  1:
else
  Gk(k,a-1,b)+Gk(k,a,b-1):
fi:

end:


#CONJECTURE: Gk(1,a,b) = (a+b+1)(a+b)*...*(a+3)*(a-(b-2))/b! for a>=b-1
#CONJECTURE: Gk(2,a,b) = (a+b)(a+b-1)*...*(a+4)*(a-(b-3))/b! for a>=b-2
#VerifyGk: Proves above conjectures.
VerifyGk:=proc() local H1,H2,x,y,i1,i2,i3,j1,j2,j3:

H1:=(a,b)->product(a+b+1-i,i=0..b-2)*(a-(b-2))/b!:
H2:=(a,b)->product(a+b-i,i=0..b-4)*(a-(b-3))*(a^2+(b+3)*a+b^2+2)/b!:

i1:=simplify(H1(x,x+1)-H1(x,x)):
i2:=simplify(H1(x-1,y)+H1(x,y-1)-H1(x,y)):
i3:=simplify(H1(x,0)-1):

j1:=simplify(H2(x,x+2)-H2(x,x+1)):
j2:=simplify(H2(x-1,y)+H2(x,y-1)-H2(x,y)):
j3:=simplify(H2(x,0)-1):

evalb({i1,i2,i3,j1,j2,j3} = {0}):
end:



#Gk1k2(k1,k2,a,b): the number of walks from [0,0] to [a,b]
#using positive unit steps ([1,0], [0,1]) always
#staying in the safe region -k1<=a-b<=k2
Gk1k2:=proc(k1,k2,a,b) option remember:

if a-b<-k1 or a-b>k2 then
  0:
elif a=0 or b=0 then
  1:
else
  Gk1k2(k1,k2,a-1,b)+Gk1k2(k1,k2,a,b-1):
fi:

end:


#CONJECTURE: Gk1k2(1,1,a,a) = 2^a.
#CONJECTURE: Gk1k2(2,2,a,a) = 2*3^a, for a>0.
#CONJECTURE: Gk1k2(3,3,a,a) = f(a) satisfies f(a) = 4*f(a-1)-2*f(a-2).  (courtesy of oeis)


#F3(a,b,c): the number of walks from [0,0,0] to [a,b,c]
#using positive unit steps ([1,0,0], [0,1,0], [0,0,1])
F3:=proc(a,b,c) option remember:

if a<0 or b<0 or c<0 then
   0:
elif nops(subs(0=NULL,[a,b,c]))=0 or nops(subs(0=NULL,[a,b,c]))=1 then
   1:
else
  F3(a-1,b,c)+F3(a,b-1,c)+F3(a,b,c-1):
fi:

end:


#G3(a,b,c): the number of walks from [0,0,0] to [a,b,c]
#using positive unit steps ([1,0,0], [0,1,0], [0,0,1])
#always staying in the safe region a>=b>=c.
G3:=proc(a,b,c) option remember:

if a<0 or b<0 or c<0 or a<b or b<c then
   0:
elif nops(subs(0=NULL,[a,b,c]))=0 or nops(subs(0=NULL,[a,b,c]))=1 then
   1:
else
  G3(a-1,b,c)+G3(a,b-1,c)+G3(a,b,c-1):
fi:

end: