MVR4
I#ct:6'%(SUMMANDG%&ORDERG%"kG%"nG%"NG6G%#guG%"iG%$opeG%%POL1G%)SUMMAND1G%'yakha
sG%"PG%"QG%"RG%"jG%%res1G%#kvG%&hakhiG%"gG%#A1G%#B1G%#P1G%$SDZG%%SDZ1G%%deggG%#
eqG%#fuG%%guguG%#i1G%$ia1G%#k1G%'kvutsaG%#l1G%#l2G%&meka1G%&mekb1G%%mumuG%$va1G
%$va2G%%ope1G%'denFACG%&ope1aG6"FPCL@$09#""&-%&ERRORG6#%^oSyntax:~ct(SUMMAND,OR
DER,summation_variable,auxiliary_var,~Shift_n)G@$/-%%tovuG6%-%(convertG6$9$%*fa
ctorialG9&9'""!-FW6'%EThe~summand~can~be~seperated~into~f(GF^o%$)g(GF_o%")G>8&F
`o?(8%F`o"""9%%%trueG>Fgo,&FgoFjo*&(%$bpcGFioFjo)9(FioFjoFjo>8$-%&hafelG6'FjoFi
nFgoF_oFcp>8'&Fep6#Fjo>8(&Fep6#""#>8G&Fep6#""$>8)-%*simplify1G6%F^qF^o!"">Fhq-%
'normalG6#*$FhqF\r>84Fjo>8+-%&numerG6#Fhq>8,-%&denomGFhr>8.-%(findgQRG6&FerFjrF
^o"$+"?(FPFjoFjoFP0&F^sF`qF`oC(>81&F^sF\q>80Fes>Fer-F_r6#*&FerFjoFhsF\r>Fjr-F_r
6#*&FjrFjo-%%subsG6$/F^o,&F^oFjoF[tF\rFhsF\r>Fcr*&FcrFjo-%(productG6$-Fet6$/F^o
,&F^oFjo8;F\rFhs/Fbu;F`o,&F[tFjoF\rFjoFjo>F^sF_s>8**&FjpFjoFcrFjo>82,&-Fet6$/F^
o,&F^oFjoFjoFjoFerFjoFjrFjo>F[v-%'expandG6#F[v>83,&F]vFjoFjrF\r>Ffv-Fcv6#Ffv>8?
-%'degreeG6$F[vF^o@%/FfvF`o>8@!$+">Fcw-F^w6$FfvF^o>8A-%&coeffG6%F[vF^oF\w>8B-F[
x6%FfvF^oFcw@(1F\wFcw>8=,&-F^w6$FhuF^oFjoFcwF\r/Fcw,&F\wFjoF\rFjoC$>8C,$*&F^xFj
oFiwF\r!"#@%-%%typeG6$F\y%(integerG>Fdx-%$maxG6$F\y,(FfxFjoF\wF\rFjoFjo>FdxFiy2
FcwFix>Fdx-Fgy6$F`oFiy>89F`o@$2FdxF`o-%'RETURNG6#F`o@$1F`oFdxC1?(8<F`oFjoFdxF\p
>F`z,&F`zFjo*&(%$apcGFjzFjo)F^oFjzFjoFjo>8:,(*&F]vFjoF`zFjoFjo*&FjrFjo-Fet6$/F^
o,&F^oFjoF\rFjoF`zFjoF\rFhuF\r>Fb[l-Fcv6#Fb[l>87-F^w6$Fb[lF^o?(FjzF`oFjoF^\lF\p
>&886#,&FjzFjoFjoFjo/-F[x6%Fb[lF^oFjzF`o?(FjzF`oFjoFdxF\p>&8DFe\lF^[l?(FjzF`oFj
oF[pF\p>&8EFe\l(FapFjz>Fd\l-Fjn6$Fd\l%$setG>F]]l-Fjn6$F]]lFf]l>Fa]l-Fjn6$Fa]lFf
]l>F]]l-%&unionG6$F]]lFa]l>F]]l-%'solve1G6$Fd\lF]]l>8><#F]]l>F`z-Fet6$F]]lF`z>F
go-Fet6$F]]lFgo@$55/FgoF`o/Ff^l<"/F`zF`oFcz>FepFc_l?(FbuF`oFjoFdxF\p>Fep-F_^l6$
Fep<#/(F_[lFbuFjo?(FbuF`oFjoF[pF\p>Fep-F_^l6$Fep<#/(FapFbuFjo>F`z-Fet6$FepF`z>F
go-Fet6$FepFgo>Fgo-%'pashetG6$FgoFcp>8F*&FgoFjo-F\s6#FgoFjo>85*,FaalFjoF]vFjoF`
zFjoFcrF\rFcqF\r>86*&-Fet6$Fh[lFdalFjo-Fjq6%FinF^oF\rFjo>Fgal-%)simplifyG6#Fgal
>8HF`o?(FioF`oFjo-F^w6$F_alFcpF\p>Fbbl,&FbblFjo-%%sortG6#*&-F[x6%F_alFcpFioFjoF
bpFjoFjo-Fdz6$FbblFgalFPFPFP,
I'paper3:6(F%F'F(F)FMF=FPFPFPC<-%'lprintG6#%!G-Fecl6#%8A~PROOF~OF~A~RECURRENCEG
Fdcl-Fecl6#%hnBy~Shalosh~B.~Ekhad,~Temple~University,~ekhad@math.temple.eduGFdc
l-Fecl6%%,Theorem:LetG-%"FG6$F^oF[p%,be~given~byGFdcl-%&printG6#F\oFdcl-Fecl6'%
(and~letG-%$SUMG6#F^o%.be~the~sum~ofGFadl%&~withG-Fecl6%%+respect~toGF[p%".GFdc
l-Fecl6$F[el%T~satisfies~the~following~linear~recurrence~equationGFdcl-Ffdl6#-%
%yafeG6&FcpF_oF^oF[el-Ffdl6#%$=0.GFdcl-Fecl6%%=PROOF:~We~cleverly~constructG-%"
GGFcdl%#:=GFdcl-Ffdl6#*&9)FjoF\oFjo-Fecl6#%5with~the~motive~thatGFdcl-Ffdl6#-Fj
el6&FcpF_oF^oFadl-Fecl6%%"=G,&-Fcfl6$F^o,&F[pFjoFjoFjoFjoFbflF\r%)(check!)GFdcl
-Fecl6%%Uand~the~theorem~follows~upon~summing~with~respect~toGF[p%&.QED.GFPFPFP,
I'AZpapc:6%%*INTEGRANDG%"yG%"xG6&%"DGF=F+FMFPFPC&>Fgo-%$AZcG6&F\oF[pF^oFep>Fjp&
FgoF\q>Fio&FgoF`q-%'papercG6(F\oF[pF^oFepFjpFioFPFPFP,
I'AZpapd:6%F_hlFahlF(FbhlFPFPC&>Fgo-%$AZdGFhhl>FjpFjhl>FioF\il-%'paperdGF_ilFPF
PFP,
I'pashet:6$%"pGF)6&F,%$gu1GF+%#p1GFPFPC)>Fjp-F_rFgdl>Fio-F\s6#Fjp>Fjp-FgrFgjl>F
jp-FcvFgjl>FgoF`o?(FepF`oFjo-F^w6$F\oF[pF\p>Fgo,&FgoFjo*&-%'factorG6#-F[x6%FjpF
[pFepFjo)F[pFepFjoFjo-Fdz6#*&FgoFjoFioF\rFPFPFP,
I(pashetc:6$F^jlFchl6&F+FajlF,%%mekhGFPFPC)>FioFdjl>Fjp-F\s6#Fio>Fio-FgrFe\m>Fi
o-FcvFe\m>FepF`o?(FgoF`oFjo-F^w6$FioF[pF\p>Fep,&FepFjo*&-Fd[m6#-F[x6%FioF[pFgoF
jo)F[pFgoFjoFjo-Fdz6$FepFjpFPFPFP,
I(pashetd:F]jl6&F+FajlF`\mF,FPFPC)>FioFdjl>FgoFd\m>FioFg\m>FioFi\m>FepF`o?(FjpF
`oFjoF\]mF\p>Fep,&FepFjo*&-Fd[m6#-F[x6%FioF[pFjpFjo)F[pFjpFjoFjo-FdzFi`lFPFPFP,
I'paperc:6(F_hlF`hlFahlFchlFMF=FPFPFPC=-Fecl6#%fnA~PROOF~OF~A~DIFFERENTIAL~EQUA
TION~SATISFIED~BY~AN~INTEGRALGFdclF[dlFdcl-Fecl6#%SI~will~give~a~short~proof~of
~the~following~result.GFdclF^dlFdclFedlFdcl-Fecl6'Fjdl-%)INTEGRALGF]el%3be~the~
integral~ofGFadlF_elF`elFdcl-Fecl6$Fg_m%V~satisfies~the~following~linear~differ
ential~equationGFdcl-Ffdl6#-%&yafecG6&FcpF_oF^oFg_mF\flFdclF_flFdclFeflFiflFdcl
-Ffdl6#-F``mF_gl-Fecl6%Fbgl-%%diffG6$FbflF[pFgglFdcl-Fecl6%%Yand~the~theorem~fo
llows~upon~integrating~with~respect~toGF[pF[hlFPFPFP,
I'paperd:6(F_hlFahlF(F)FMF=FPFPFPC>Fdcl-Fecl6#%XA~PROOF~OF~A~LINEAR~RECURRENCE~
SATISFIED~BY~AN~INTEGRALGFdclF[dlFdclFb_mFdclF^dlFdclFedlFdclFe_mF`elFdcl-Fecl6
$Fg_mFfelFdcl-Ffdl6#-FjelFa`mF\flFdclF_flFdclFeflFiflFdclF\gl-Fecl6$FbglFg`mFdc
lFj`mFPFPFP,
I%ezra:FPFPFPFPC-@$/9"%%NULLGC--Ffdl6#%&EKHADG-Ffdl6#%fnA~Maple~package~for~pro
ving~Hypergemetric~(Binomial~Coeff.)G-Ffdl6#%?~and~other~kinds~of~identitiesG-F
fdl6#%hnThis~version~(Feb,~25,~1999)~is~much~faster~than~the~previousG-Ffdl6#%_
oversion,~thanks~to~a~SLIGHT~(yet~POWERFUL)~modification~suggested~byG-Ffdl6#%2
~FREDERIC~CHYZAK~GFdcl-Ffdl6#%[oFor~help~with~a~specific~procedure,~type~"ezra(
procedure_name);"G-Ffdl6#%6Contains~procedures:~G-Ffdl6#%gnfindrec,ct,zeil,zeil
pap,zeillim,AZd,AZc,AZpapd,AZpapc,celineG-Ffdl6#%?show_ct,show_zeil,show_zeilli
mG@$3/-%%nopsG6#7#F`bmFjo/-%#opG6$FjoFgdm%'celineGC+-Ffdl6#%]oceline(FUNCTION,O
RDER_n,ORDER_k)~applies~Sister~Celine's~techniqueG-Ffdl6#%jnIt~inputs~a~functio
n~(n,k)->FUNCTION,~and~the~guessed~orders~inG-Ffdl6#%gnn~and~k,~ORDER_n,ORDER_k
~respectively,~and~outputs~a~partialG-Ffdl6#%2k-free~recurrenceG-Ffdl6#%Vit~~al
so~finds~the~telescoped~form~of~the~recurrence.G-Ffdl6#%fn~In~input,~do~not~rai
se~products~of~factorials~to~powers;~~G-Ffdl6#%Linstead~raise~each~factorial~to
~the~power.~G-Ffdl6#%NFor~example:celine((n,k)->binomial(n,k),1,1);G-Ffdl6#%Xce
line~((n,k)->n!*(2*k)!*(-2)^(n-k)/(k!^3*(n-k)!),2,2);G@$3Fcdm/Fidm%(findrecGC,-
Ffdl6#%`ofindrec(f,DEG,ORDER,n,N)~finds~empirically~an~ordi.~linear~recurrenceG
-Ffdl6#%]o~with~polynomial~coeffs.~The~input~is~a~sequence~f~given~as~a~listG-F
fdl6#%MSTARTING~at~f[1],i.e.~f[0]~is~not~consideredG-Ffdl6#%S~where~DEG:=the~ma
ximal~degree~of~the~coefficientsG-Ffdl6#%^oand~ORDER:=the~order~of~the~recurren
ce.~~The~output~is~the~operatorG-Ffdl6#%in~in~n~and~N,~where~N~is~the~forward~u
nit~shift:~Nf(n):=f(n+1).G-Ffdl6#%[oFor~example~findrec([1,1,2,3,5,8,13,21,34],
0,2,n,N)~should~yieldG-Ffdl6#%\oN^2-N-1~,~and~findrec([1,2,5,14,42,132,429],1,1
,m,M)~should~yieldG-Ffdl6#%hn(m+1)*M-(4*m-2).~If~there~is~not~enough~data,~you~
will~get~anG-Ffdl6#%enan~error~message.~If~there~is~no~operator,~you~would~get~
0G@$3Fcdm/FidmF\hlC1-Ffdl6#%XAZpapc(INTEGRAND,y,x)~inputs~a~hypergeometric~inte
grandG-Ffdl6#%`oin~the~continuous~variables~y~and~x~(i.e.~the~logarithmic~deriv
ativesG-Ffdl6#%jndiff(INTEGRAND,x)/INTEGRAND~and~diff(INTEGRAND,y)/INTEGRAND~ar
eG-Ffdl6#%?rational~functions~in~x~and~y)G-Ffdl6#%_oand~outputs~a~paper~with~a~
proof~of~the~linear~differential~equationG-Ffdl6#%\othat~the~definite~integral~
w.r.t.~to~y~(which~is~a~function~of~x)G-Ffdl6#%Asatisfies.~It~uses~the~method~o
fG-Ffdl6#%]oGert~Almkvist~and~Doron~Zeilberger,~"The~method~of~differentiatingG
-Ffdl6#%_ounder~the~integral~sign",~J.~Symbolic~Computation~10(1990),~571-591.G
Fdcl-Ffdl6#%TIt~could~be~used~to~establish~the~diff.~eq.~of~the~G-Ffdl6#%[oclas
sical~orthogonal~polynomials,~when~they~are~defined~in~termsG-Ffdl6#%=or~their~
generating~funtion.G-Ffdl6#%hnFor~example~AZpapc(1/sqrt(1-2*x*t+t^2)/t^(n+1),t,
x)~gives~theG-Ffdl6#%jnthe~differential~equation~satisfied~by~the~Legendre~poly
nomialsG@$3Fcdm/FidmF`ilC4-Ffdl6#%XAZpapd(INTEGRAND,x,n)~inputs~a~hypergeometri
c~integrandG-Ffdl6#%Yin~the~continuous~variable~x~and~the~discrete~variable~nG-
Ffdl6#%^oi.e.~i.e.~A(x,n+1)/A(x,n)~and~A'(x,n)/A(x,n)~are~rational~functionsG-F
fdl6#%+of~(x,n)),G-Ffdl6#%]oand~outputs~a~paper~with~a~proof~of~the~linear~recu
rrence~equationG-Ffdl6#%\othat~the~definite~integral~w.r.t.~to~y~(which~is~a~fu
nction~of~n)G-Ffdl6#%jnassuming~that~the~integrand~(or~rather~it~times~the~cert
ificateG-Ffdl6#%Yvanishes~at~the~endpoints,~or~it~is~a~~contour~integralsG-Ffdl
6#%jnsatisfies.~It~assumes~the~following:~A(x,n)~is~not~a~product~ofG-Ffdl6#%Go
f~a~function~of~n~and~a~function~of~xG-Ffdl6#%6It~uses~the~method~ofGFejm-Ffdl6
#%^ounder~the~integral~sign",~J.~Symbolic~Computation~10(1990),~571-591G-Ffdl6#
%VIt~could~be~used~to~establish~the~recurrences~of~the~GF^[n-Ffdl6#%<or~their~g
enerating~funtionG-Ffdl6#%hnFor~example~AZpapd(1/sqrt(1-2*x*t+t^2)/t^(n+1),t,n)
~gives~theG-Ffdl6#%[othe~recurrence,~and~proof,~satisfied~by~the~Legendre~polyn
omialsG@$3Fcdm/FidmFfilC3-Ffdl6#%RAZd(A,x,n,N)~finds~a~recurrence~of~order~ORDE
R<=8G-Ffdl6#%Mphrased~in~terms~of~n,~and~the~shift~in~n,~NG-Ffdl6#%\ofor~the~in
tegrale~of~A(x,n)~with~respect~to~x,~whenever~A(x,n)~isG-Ffdl6#%^ohypergeometri
c~in~(x,n),i.e.~A(x,n+1)/A(x,n)~and~A'(x,n)/A(x,n)~areG-Ffdl6#%Zrational~funtio
ns~of~x~and~n.~It~follows~the~algorithn~ofGFejmF_^n-Ffdl6#%\oA~should~not~be~a~
product~of~a~function~of~x~and~a~function~of~n.G-FfdlFfcl-Ffdl6#%fnAZd(A,x,n,N)
~returns~the~expression~seq.~ope(n,N),cert(x,n)G-Ffdl6#%Tsatisfying~ope(n,N)A(x
,n)=diff(cert(x,n)*A(x,n),x).G-Ffdl6#%IIf~no~recurrence~is~found,~it~returns~0.
GFd`n-Ffdl6#%]oA~verbose~version~is~AZpapd(A,x,n),~type~ezra(AZpapd)~for~detail
s.GFd`n-Ffdl6#%YFor~example~AZd(1/sqrt(1-2*x*t+t^2)/t^(n+1),t,n,N)~givesG-Ffdl6
#%`othe~diff.eq.,~and~proof~certificate,~for~the~Legendre~polct:ynomials.G@$3Fc
dm/FidmFghlC/-Ffdl6#%fnAZc(A,y,x,D)~tries~to~finds~a~linear~diff.eq.~of~order~<
=8,G-Ffdl6#%L~phrased~in~terms~of~x,~and~diff.w.r.t~x,~DG-Ffdl6#%\ofor~the~inte
grale~of~A(x,y)~with~respect~to~x,~whenever~A(x,y)~isG-Ffdl6#%`ohypergeometric~
in~(x,y),i.e.~~A_x(x,y)/A(x,y)~and~A_y(x,y)/A(x,y)~areG-Ffdl6#%Zrational~funtio
ns~of~x~and~y.~It~follows~the~algorithn~ofGFejmF_^n-Ffdl6#%fnAZc(A,y,x,D)~retur
ns~the~expression~seq.~ope(x,D),cert(x,n)G-Ffdl6#%Tsatisfying~ope(x,D)A(x,y)=di
ff(cert(x,y)*A(x,y),y).G-Ffdl6#%ZIf~no~linear~diff.~eq.~of~order<=8~is~found,~i
t~returns~0G-Ffdl6#%Bsee~AZpapc~for~a~verbose~vsersionG-Ffdl6#%gnFor~example~AZ
c(1/sqrt(1-2*x*t+t^2)/t^(n+1),t,x,D)~gives~theG-Ffdl6#%\othe~diff.eq.,~and~proo
f~certificate~for~the~Legendre~polynomials.G@$3Fcdm/FidmF"C4-Ffdl6#%9~ct(SUMMAN
D,ORDER,k,n,N)G-Ffdl6#%]oThis~is~a~Maple~inplementation~of~the~algorithm~descri
bed~in~Ch.~6G-Ffdl6#%]oof~the~book~A=B,~first~proposed~in~:~D.~Zeilberger,~"The
~method~ofG-Ffdl6#%\oof~creative~telescoping",~J.Symbolic~Computation~11(1991)~
195-204GFd`n-Ffdl6#%gnfinds~a~recurrence~for~SUMMAND~in~the~parameters~k~and~n,
~~~G-Ffdl6#%[o~of~order~ORDER,~with~N~is~the~chosen~symbol~for~the~shift~in~n.G
Fd`n-Ffdl6#%[oSUMMAND~should~be~a~product~of~factorials~and/or~binomial~coeffsG
-Ffdl6#%fnand/or~rising~factorials,~where~(a)_k~is~denoted~by~rf(a,k)G-Ffdl6#%i
nand/or~powers~of~k~and~n,~and,~optionally,~a~polynomial~factorG-Ffdl6#%_oThe~o
utput~consists~of~an~operator~ope(N,n)~and~a~certificate~R(n,k)G-Ffdl6#%\owith~
the~properties~that~if~we~define~G(n,k):=R(n,k)*SUMMAND~thenG-Ffdl6#%Eope(N,n)S
UMMAND(n,k)=G(n,k+1)-G(n,k)G-Ffdl6#%Jwhich~is~a~routinely~verifiable~identity.G
-Ffdl6#%jnFor~example~"ct(binomial(n,k),1,k,n,N);"~would~yield~the~outputG-Ffdl
6#%2~~N-2,~k/(k-n-1)~G-Ffdl6#%[pshow_ct(SUMMAND,ORDER,k,n,F,G)~gives~the~recurr
ence~for~F(n,k)~in~classical~formG@$3Fcdm/Fidm%%zeilGC9-Ffdl6#%)Like~ct,G-Ffdl6
#%]othis~is~a~Maple~inplementation~of~the~algorithm~described~in~Ch.~6GFfdn-Ffd
l6#%KBut~it~is~not~necessary~to~guess~the~ORDERG-Ffdl6#%Z~zeil(SUMMAND,k,n,N)~o
r~zeil(SUMMAND,k,n,N,MAXORDER)~or~~G-Ffdl6#%N~zeil(SUMMAND,k,n,N,MAXORDER,param
eter_list)~G-Ffdl6#%V~finds~a~linear~recurrence~equation~for~SUMMAND,~withG-Ffd
l6#%9~polynomial~coefficientsG-Ffdl6#%Wof~ORDER<=MAXORDER,~where~the~default~of
~MAXORDER~is~6G-Ffdl6#%Tin~the~parameter~n,~the~shift~operator~in~n~being~NG-Ff
dl6#%Lof~the~form~ope(N,n)SUMMAND=G(n,k+1)-G(n,k)G-Ffdl6#%^owhere~G(n,k):=R(n,k
)*SUMMAND,~and~R(n,k)~is~the~2nd~item~of~output.G-Ffdl6#%@The~output~is~ope(N,n
),R(n,k)~.G-Ffdl6#%RFor~example~zeil(binomial(n,k),k,n,N)~would~yieldG-Ffdl6#%3
~~N-2,~k/(k-n-1)~~G-Ffdl6#%hn~in~which~N-2~is~the~"ope"~operator,~and~k/(k-n-1)
~is~R(n,k)~GFbenFeen-Ffdl6#%jnand/or~powers~in~k~and~n,~and,~optionally,~a~poly
nomial~factor.GFdcl-Ffdl6#%hnThe~last~optional~parameter,~is~the~list~of~other~
parameters,G-Ffdl6#%[oif~present.~Giving~them~causes~considerable~speedup.~For~
exampleG-Ffdl6#%in~zeil(binomial(n,k)*binomial(a,k)*binomial(b,k),k,n,N,6,[a,b]
)G@$3Fcdm/Fidm%(zeilpapGC*-Ffdl6#%W~zeilpap(SUMMAND,k,n)~or~zeilpap(SUMMAND,k,n
,NAME,REF)G-Ffdl6#%QJust~like~zeil~but~writes~a~paper~with~the~proofG-Ffdl6#%MN
AME~and~REF~are~optional~name~and~referenceG-Ffdl6#%YWarning:~It~assumes~that~t
he~definite~summation~w.r.t.~kG-Ffdl6#%gnextends~over~all~k~where~it~is~non-zer
o,~and~that~it~is~zeroG-Ffdl6#%,for~other~kG-Ffdl6#%NFor~non-natural~summation~
limits,~use~zeillimG-Ffdl6#%coshow_zeil(SUMMAND,k,n,S)~gives~the~recurrence~for
~S(n)~in~classical~formG@$3Fcdm/Fidm%(zeillimGC,-Ffdl6#%D~zeillim(SUMMAND,k,n,N
,alpha,beta)~G-Ffdl6#%gnSimilar~to~zeil(SUMMAND,k,n,N)~but~outputs~a~recurrence
~for~G-Ffdl6#%O~the~sum~of~SUMMAND~from~k=alpha~to~k=n-beta~.G-Ffdl6#%\oOutputs
~the~recurrence~operator,~certificate~and~right~hand~side.G-Ffdl6#%`oNote~caref
ully:~The~upper~limit~of~the~sum~will~be~n-beta,~not~beta.~G-Ffdl6#%\oFor~examp
le,~"zeillim(binomial(n,k),k,n,N,0,1);"~gives~output~of~G-Ffdl6#%3~N-2,~k/(k-n-
1),1~G-Ffdl6#%Z~which~means~that~SUM(n):=2^n-1~satisfies~the~recurrence~G-Ffdl6
#%S~(N-2)SUM(n)=1,~as~certified~by~R(n,k):=k/(k-n-1)~G-Ffdl6#%apshow_zeillim(SU
MMAND,k,n,S,alpha,beta)~gives~the~recurrence~for~S(n)~in~classical~formGFPFPFP,
I&zeil4:6&F%F'F(F)6'F&%)MAXORDERGF+F`jl%%reshGFPFPC'>Fio""'>F^q7"@$/-Fjq6%F\oF^
oFjoFjo-FW6%%;Summand~does~not~depend~onGF^o%G~hence~the~sum~is~identically~con
stantG?(FepF`oFjoFioF\pC$>Fjp-%&cttryG6(F\oFepF[pF^oF^qF_o@$/FjpFjoC$>Fgo-F"6'F
\oFepF[pF^oF_o@$0FgoF`o-FdzFbal-FW6%%9No~recurrence~of~order<=GFio%*was~foundGF
PFPFP,
I&zeil5:6'F%F'F(F)Fb_o6&F&F+F`jlFc_oFPFPC&>FjpFh_o@$Fj_oF]`o?(FepF`oFjoFcpF\pC$
>Fgo-Fe`o6(F\oFepF[pF^oFjpF_o@$/FgoFjoC$>FioF[ao@$0FioF`o-FdzFe\m-FW6%FbaoFcpFc
aoFPFPFP,
I&zeil6:6(F%F'F(F)Fb_oFc_o6%F&F+F`jlFPFPC%@$Fj_oF]`o?(FepF`oFjoFcpF\pC$>Fgo-Fe`
o6(F\oFepF[pF^oFhflF_o@$FaboC$>FioF[ao@$FeboFfboFgboFPFPFP,
I(zeillim:6(F%F'F(F)%&alphaG%%betaG6*F-%%CERTG%#luGFDF,F+%$lu1G%$lu2GFPFPC->Fhq
-%(ZeillimG6(F\oF[pF^oF_o,&FcpFjoFjoFjo,&FhflFjoFjoFjo>Fep&FhqF\q>Fio&FhqF`q>Fg
o&FhqFeq>Fhu,&-Fet6$/F[pFcpF\oFjo-Fet6$/F[p,&F^oFjoFhflF\rF\oFjo>Fhu-F_bl6#Fhu>
Fhu-F_rFjeo>FerF`o?(F^qF`oFjo-F^w6$FepF_oF\p>Fer,&FerFjo*&-F[x6%FepF_oF^qFjo-F_
bl6#-Fet6$/F^o,&F^oFjoF^qFjoFhuFjoFjo>Fer-F_r6#Fer6%FepFio-F_r6#-Fcv6#-F_r6#-F_
bl6#-Fcv6#-F_r6#,&FgoFjoFerFjoFPFPFP,
I-show_zeillim:6(%"fGF'F(%"SG%#k0GFD6%%$solGF)F,FPFPC$>Fep-F^]o6(F\oF[pF^oFioFc
pFhfl/-%$sumG6$*&-F[x6%F[qFioFgoFjo-F_o6#,&F^oFjoFgoFjoFjo/Fgo;F`o-F^w6$F[qFio-
Fd[m6#FdqFPFPFP,
I(zeilpap:FPFPFPFP@'/FTFU-%)zeilpap5G6#F`bm/FTFfq-%)zeilpap3GF_jo-FW6#%Wzeilpap
(SUMMAND,k,n,NAME,REF)~or~~zeilpap(SUMMAND,k,n)GFPFPFP,
I(show_ct:6(F`ho%&ordreGF'F(FbdlFcflFchoFPFPC$>Fep-F"6'F\oF[pF^oF_oFio6$/-F[io6
$*&F^ioFjo-Fcp6$,&F_oFjoFgoFjoF^oFjoFcio,&-Fhfl6$F_oF`vFjo-Fhfl6$F_oF^oF\r/Fi[p
-Fd[m6#*&F_qFjoF\oFjoFPFPFP,
I&hafel:6'%$POLGF%F-F(F)6*F,%$FACGF>%#biG%$ratGF.F/%$zubGFPFPC)>Fgo-F^w6$F^oFcp
>FioF`o?(FepF`oFjoFgoF\pC&>Fjp-F[x6%F^oFcpFep>F^q-Fjq6%F[pF_oFep>Fio,&FioFjo*(F
jpFjo-Fet6$/F_o,&F_oFjoFepFjoF\oFjoF^qFjoFjo>Fio-F_rFe\m>FhqFg\m>FerFd\m>Fhu*&F
[pFjoFerF\r-Fdz6%FhqFhuFerFPFPFP,
I&paper:6*F%F'F(F)FMF=%%NAMEG%$REFG6%%%SHEMG%)IDENTITYG%+RECURRENCEGFPFPC@@%/-F
^w6$FcpF_oFjo>FepFio>FepFgoFdcl-Fecl6%%/A~PROOF~OF~THEG9*FepFdclF[dlFdcl-Fecl6%
%SI~will~give~a~short~proof~of~the~following~result(G9+%#).GFdcl@$F__pC&-Fecl6#
%en(Note~that~since~the~recurrence~below~is~first~order,~thisG-Fecl6%%3means~th
at~the~sumGF[el%:has~closed~form,and~it~isG-Fecl6#%?easily~seen~to~be~equivalen
t.)GFdclF^dlFdclFedlFdclFhdlF`elFdclFdelFdclFgelF\flFdclF_flFdclFeflFiflFdclF\g
lF`glFdclFhglFPFPFP,
I(findgQR:6&F2F3F'%"LG6$F4F8FPFPC$?(FepFjoFjoF_oF\pC$>Fio-%$gcdG6$F\o-Fet6$/F^o
,&F^oFjoFepFjoF[p@$2F`o-F^w6$FioF^o-Fdz6$FioFep6$FjoF`oFPFPFP,
I-solve/linear:FP6'F'Fdho%%notzG%%eqnsG%%varsG6#%aoCopyright~(c)~1992~by~the~Un
iversity~of~Waterloo.~All~rights~reserved.GFPC.>Fjp&F`bmF\q>F^q&F`bmF`q@$-Fby6$
Fjp%%listG>Fjp<#-FjdmFgjl@$-Fby6$F^qF`cp>F^q<#-Fjdm6#F^q>Fjp-%$mapG6$:6#%"eGFPF
PFP@%-Fby6$F\oFbgl,&-%$lhsGFgdlFjo-%$rhsGFgdlF\rF\oFPFPFjp@$4-Fby6$Fjp-Ff]l6#%*
algebraicG-FW6#%hn1st~argument~must~be~a~list~or~set~of~polynomials~(equations)
G@$4-Fby6$F^q-Ff]l6#%%nameG-FW6#%W2nd~argument~must~be~a~list~or~set~of~names~(
unknowns)G?&FepFjpF\p@$54-Fby6$Fep-%(polynomG6$%)anythingGF^q2Fjo-F^w6$FepF^q-F
dz6#%%FAILG-%)userinfoG6&Fjo%&solveG%,#~equationsG-FedmFgjl@9-Fby6$Fjp-Ff]l6#-F
efp6$%)rationalGF^q>Fio--%(readlibG6#%5solve/linear/integerG6$FjpF^q-Fby6$Fjp-F
f]l6#-Fefp6$%(numericGF^q>Fio--F_hp6#%3solve/linear/floatGFbhp-Fby6$Fjp-Ff]l6#-
Fefp6$-%(complexG6#FihpF^q>Fio--F_hp6#%5solve/linear/complexGFbhp-Fby6$Fjp-Ff]l
6#-%(ratpolyG6#F[hp>Fio--F_hp6#%5solve/linear/polynomGFbhp-Fby6$Fjp-Ff]l6#-Fefp
6$%'algnumGF^q>Fio--F_hp6#%4solve/linear/algnumGFbhp-Fby6$Fjp-Ff]l6#-Fefp6$%'ra
dnumGF^q>Fio--F_hp6#%4solve/linear/radnumGFbhp-Fby6$Fjp-Ff]l6#-Fbjp6#F_[q>Fio--
F_hp6#%5solve/linear/polyalgGFbhp-Fby6$Fjp-Ff]l6#-Fbjp6#F[\q>FioF]\q-Fby6$Fjp-F
f]l6#-%'algfunGFcjp>Fio--F_hp6#%4solve/linear/algfunGFbhp-Fby6$Fjp-Ff]l6#-%'rad
funGFcjp>Fio--F_hp6#%4solve/linear/radfunGFbhp-%(hastypeG6$Fjp%&floatGC%>Fjp-Fj
n6%-%&evalfGFgjlF[hp%&exactG>Fio-F`bp6%FjpF^q&F`bm6#;FfqFT@$0FioFabm>Fio-Fb_qFe
\m>Fio--F_hp6#%3solve/linear/fieldGFbhp@%/FTFaqFfbo>Fgo-Fet6$Fio&F`bmFeq@'-%'me
mberG6$F`oFgoFP-F[aq6$F`o-F]dp6$F_rFgoFPFioFPFP6",
I&duisc:6'%"AGF&F`hlFahlFchl6?%%KAMAG%&goremG%%conjGF0%%lu1aG%$LU1GF1F2F3Faho%#
j1GF8%#Q1G%#Q2GFFFGFJFIF@FHFDFAF?FCFKFLF>F,%%shadGFPFPCV>Fep"#5>Fio-%'goremcG6$
FcpF[p>FgoFio>FjpF`o?(F\wF`oFjo-F^wF]alF\pC$>Fjp,&FjpFjo-F_r6#*(-F[x6%FgoFcpF\w
Fjo-%%gzorG6%F\oF_oF\wFjoF\oF\rFjo>Fjp-F_rFgjl>F^qFjp>FhqFijl>Fjp*$FfjlF\r>Fjp-
F_r6#,&*&-Fh`m6$FjpF^oFjoFjpF\rFjo*&-Fh`m6$F\oF^oFjoF\oF\rFjo>FhuFhq>FerFijl>Fj
rFfjl>F^sF`o?(FPFjoFjoFP1F^sFepC%>8/-Fcap6$Fjr,&FerFjo*&F^sFjo-Fh`m6$FjrF^oFjoF
\r@$0F^eqFjoC'>Fhs*&FaeqFjoF^eqF\r>Fjr-F_r6#*&FjrFjoF^eqF\r>Fer-F_r6#,&FhsFjoFb
eqFjo>Fhu*&FhuFjo)F^eqF^sFjo>F^sF\r>F^s,&F^sFjoFjoFjo>Fhu-FcvFjeo>Fjr-Fcv6#Fjr>
Fer-FcvF^go>F[t,&FerFjoFceqFjo>F[t-Fcv6#F[t>F[v-F^wFdeq>Ffv-F^w6$F[tF^o>F^\l-F[
x6%FjrF^oF[v>Fdal-F[x6%F[tF^oFfv@%0,&F[vFjoF\rFjoFfv>Fd\l,&FfxFjo-Fgy6$FahqFfvF
\rC$>Fcr,$*&FdalFjoF^\lF\rF\r@%3-Fby6$FcrFdy2F`oFcr>Fd\l-Fgy6$Fcr,&FfxFjoFfvF\r
>Fd\lFbiq>FgalF`o@$2Fd\lF`oFcz?(FbuF`oFjoFd\lF\p>Fgal,&FgalFjo*&F\`lFjo)F^oFbuF
joFjo>F`z,(*&F[tFjoFgalFjoFjo*&FjrFjo-Fh`m6$FgalF^oFjoFjoFhuF\r>F`z-Fcv6#F`z>Ff
^l-F^w6$F`zF^o?(FbuF`oFjoFf^lF\p>&Fb[l6#,&FbuFjoFjoFjo/-F[x6%F`zF^oFbuF`o?(FbuF
`oFjoFd\lF\p>&FjzF[[rF\`l?(FbuF`oFjoF[pF\p>&FdxF[[rFc`l>Fb[l-Fjn6$Fb[lFf]l>Fjz-
Fjn6$FjzFf]l>Fdx-Fjn6$FdxFf]l>Fjz-F_^l6$FjzFdx>Fjz-Fc^l6$Fb[lFjz>Fgal-Fet6$FjzF
gal>Fio-Fet6$FjzFio@$3/FgalF`o/FioF`oFcz?(FbuF`oFjoFd\lF\p>Fio-Fet6$F[`lFio?(Fb
uF`oFjoF[pF\p>Fio-Fet6$Fb`lFio>Fgal-F_rF`bl>Fcw-F\\m6$FioFcp>8-*,F^qFjoFjrFjoFg
alFjo&FcwF`qFjoFhuF\r>F]^r-Fet6$FjzF]^r>F]^r-F_r6#F]^r>F]^r-Fd[mFe^r?(FbuF`oFjo
Fd\lF\p>F]^r-Fet6$F[`lF]^r?(FbuF`oFjoF[pF\p>F]^r-Fet6$Fb`lF]^r6$&FcwF\qF]^rFPFP
FP,
I&duisd:6'FeaqF&F`hlF(F)6?FhaqFiaqF0FjaqF[bqF1F2F3FahoF\bqF8F]bqF^bqFFFGFJFIF@F
HFDFAF?FCFKFLF>F_bqFgaqFBFPFPCV>F\wFbbq>Fep-%'goremdGFfbq>FioFep>FgoF`o?(FcwF`o
Fjo-F^wF[^rF\p>Fgo,&FgoFjo*&-F[x6%FioFcpFcwFjo-F_bl6#*&-Fet6$/F_o,&F_oFjoFcwFjo
F\oFjoF\oF\rFjoFjo>FjpFgo>F^q-FgrFbal>Fgo*$FaalF\r>Fgo-F_r6#,&*&-Fh`m6$FgoF^oFj
oFgoF\rFjoFcdqFjo>FhqF^q>FhuF]ar>FerFaal>F]^rF`o?(FPFjoFjoFP1F]^rF\wC%>F^s-Fcap
6$Fer,&FhuFjo*&F]^rFjo-Fh`m6$FerF^oFjoF\r@$0F^sFjoC'>F[t*&FabrFjoF^sF\r>Fer-F_r
6#*&FerFjoF^sF\r>Fhu-F_r6#,&F[tFjoFbbrFjo>Fhq*&FhqFjo)F^sF]^rFjo>F]^rF\r>F]^r,&
F]^rFjoFjoFjo>Fhq-FcvFhr>FerF^gq>FhuFifq>F^eq,&FhuFjoFcbrFjo>F^eq-Fcv6#F^eq>Fhs
-F^wFdbr>F[v-F^w6$F^eqF^o>Fgal-F[x6%FerF^oFhs>Fcr-F[x6%F^eqF^oF[v@%0,&FhsFjoF\r
FjoF[v>F^\l,&-F^w6$FhqF^oFjo-Fgy6$F^erF[vF\rC$>Ffv,$*&FcrFjoFgalF\rF\r@%3-Fby6$
FfvFdy2F`oFfv>F^\l-Fgy6$Ffv,&FaerFjoF[vF\r>F^\lFafr>FdalF`o@$2F^\lF`oFcz?(Fb[lF
`oFjoF^\lF\p>Fdal,&FdalFjo*&(F_[lFb[lFjo)F^oFb[lFjoFjo>Fd\l,(*&F^eqFjoFdalFjoFj
o*&FerFjo-Fh`m6$FdalF^oFjoFjoFhqF\r>Fd\l-Fcv6#Fd\l>Fdx-F^w6$Fd\lF^o?(Fb[lF`oFjo
FdxF\p>&F`z6#,&Fb[lFjoFjoFjo/-F[x6%Fd\lF^oFb[lF`o?(Fb[lF`oFjoF^\lF\p>&FbuF[hrFj
fr?(Fb[lF`oFjoF[pF\p>&FjzF[hr(FapFb[l>F`z-Fjn6$F`zFf]l>Fbu-Fjn6$FbuFf]l>FjzFj[r
>Fbu-F_^l6$FbuFjz>Fbu-Fc^l6$F`zFbu>Fdal-Fet6$FbuFdal>Fep-Fet6$FbuFep@$3/FdalF`o
/FepF`oFcz?(Fb[lF`oFjoF^\lF\p>Fep-Fet6$/FjfrFjoFep?(Fb[lF`oFjoF[pF\p>Fep-Fet6$/
FfhrFjoFep>Fdal-F_r6#Fdal>Ff^l-Fh]m6$FepFcp>Fjr*,FjpFjoFerFjoFdalFjo&Ff^lF`qFjo
FhqF\r>Fjr-Fet6$FbuFjr>Fjr-F_rF\gq>Fjr-Fd[mF\gq?(Fb[lF`oFjoF^\lF\p>Fjr-Fet6$Fbj
rFjr?(Fb[lF`oFjoF[pF\p>Fjr-Fet6$FgjrFjr-Fdz6$&Ff^lF\qFjrFPFPFP,
I'solve1FabpFP,
I$AZc:6&FeaqF`hlFahlFchl6%F&F+FgaqFPFPC%>Fgo"")?(FepF`oFjoFgoF\pC$>Fio-FbaqF\ao
@$FeboFfboF`oFPFPFP,
I$AZd:6&FeaqF`hlF(F)Fg\sFPFPC%>FgoFj\s?(FepF`oFjoFgoF\pC$>Fio-Fb_rF\ao@$FeboFfb
oF`oFPFPFP,
I)zeilpap3:6%F%F'F(6&F=F+FMF)FPFPC&>Fio-F^_o6&F\oF[pF^oFjp>Fgo&FioF\q>Fep&FioF`
q-F`cl6(F\oF[pF^oFjpFgoFepFPFPFP,
I)zeilpap5:6'F%F'F(Fg^pFh^pF]^sFPFPC&>FioF`^s>FgoFc^s>FepFe^s-Fd^p6*F\oF[pF^oFj
pFgoFepF_oFcpFPFPFP,
I(findrec:6'F`ho%'DEGREEGF&F(F)6-F-%$varGF?%"aGF,F4%#n0GF6%%var1G%$eq1G%#muGFPF
PC/@$2-FedmFgdl,(*&FfglFjoF`vFjoFjoFaqFjoF^oFjo-FW6&%LInsufficient~data~for~a~r
ecurrence~of~orderGF^oF^wF[p>FepF`o>FioFc_l?(F^qF`oFjoF^oF\p?(FhqF`oFjoF[pF\pC$
>Fep,&FepFjo*(&Fjp6$F^qFhqFjo)F_oFhqFjo)FcpF^qFjoFjo>Fio-F_^l6$Fio<#F]as>FgoFc_
l?(FhuFjoFjo,&Fa`sFjoFaqFjoF\pC%>F]^rF`o?(F^qF`oFjoF^oF\p>F]^r,&F]^rFjo*&-Fet6$
/F_oFhu-F[x6%FepFcpF^qFjo-Fjdm6$,&FhuFjoF^qFjoF\oFjoFjo>Fgo-F_^l6$Fgo<#F]^r>Fjr
-Fc^l6$FgoFio>FerFc_l?(F^qFjoFjo-FedmF\gqF\pC$>F^s-Fjdm6$F^qFjr@$/-Fjdm6$FjoF^s
-Fjdm6$FaqF^s>Fer-F_^l6$Fer<#Ffcs>Fep-Fet6$FjrFep@$2Fjo-FedmF^goC$-Ffdl6#%E~eit
her~DEGREE~or~ORDER~are~too~highG-Ffdl6#%PThe~output~is~not~the~minimal~possibl
e~operatorG?(F^qFjoFjoFcdsF\p>Fep-Fet6$/-Fjdm6$F^qFerFjoFepFepFPFPFP,
I*show_zeil:6&F`hoF'F(FahoFchoFPFPC$>Fep-Fcgn6&F\oF[pF^oFio/FjhoF`oFPFPFP,
I'goremc:6$FchlF&6$F,F+FPFPC%>FioF`o?(FepF`oFjoF[pF\p>Fio,&FioFjo*&(FapFepFjo)F
\oFepFjoFjoFfboFPFPFP,
I'goremd:6$F)F&F]fsFPFPC%>FioF`o?(FepF`oFjoF[pF\p>FioFbfsFfboFPFPFP,
I'bdokct:6'F/F&F'F(F)6)F[`sF+F,%#G1GF-F_doF%FPFPC,>FhuFin>Fep-F"6'FhuF[pF^oF_oF
cp@$F]jrFcz>F^qF[q>Fjp*&F_qFjoFhuFjo>FioF`o?(FgoF`oFjo-F^w6$F^qFcpF\pC$>Fio,&Fi
oFjo*&-F[x6%F^qFcpFgoFjo-Fjq6%FhuF_oFgoFjoFjo>FioF]^p>Fhq,&*&-Fet6$F_vF_qFjo-Fj
q6%FhuF^oFjoFjoFjoF_qF\r>Fhq-F_rFhr-F_r6#*&FioFjoFhqF\rFPFPFP,
I*simplify1:6%%%bituGF'Fg_s6'F+F`jlF,%%khezG%#spGFPFPC&>F^qFjo>FepF\o@'-Fby6$Fe
p%"*G?(FgoFjoFjo-Fedm6#FepF\pC$>Fio-Fjdm6$FgoFep@%3-Fby6$Fio%"^G-Fby6$-Fjdm6$Fa
qFioFdyC%>FjpF`[t>Fio-Fjdm6$FjoFio>F^q*&F^qFjo)-F_bl6#*&-Fet6$/F[p,&F[pFjoF^oFj
oFioFjoFioF\rFjpFjo>F^q*&F^qFjoFj[tFjo3-Fby6$FepF][t-Fby6$-Fjdm6$FaqFepFdyC%>Fj
pFh\t>Fio-Fjdm6$FjoFep>F^qFh[t>F^q-F_bl6#*&-Fet6$F_\tFepFjoFepF\rF^qFPFPFP,
I&yafec:6&F-FchlFahlF_hl6$F+F,FPFPC%>Fep*&-F[x6%F\oF[pF`oFjoF_oFjo?(FioFjoFjoF^
[mF\p>Fep,&FepFjo*&-F[x6%F\oF[pFioFjo-Fh`m6$F_o-%"$G6$F^oFioFjoFjoFepFPFPFP,
I%gzor:6%F`hoFahlF(F]fsFPFPC%>FioF\o?(FepFjoFjoF^oF\p>Fio-Fh`mF]]mFfboFPFPFP,
I&cttry:6(F%F&F'F(Fc_oF)6CF+F,F-F.F/F0F1F2F3F4F5F6F7F8F9F:F;F>F?F@FAFBFCFDFEFFF
GFHFIFJFKFL%$eqgGFPFPC>@$0FTFf_o-FW6#%_oThe~syntax~is~cttry(term,ORDER,sum_vari
able,aux_var,para_list,Shift)G@$FenFao>FgoF`o?(FioF`oFjoF[pF\p>Fgo,&FgoFjo*&F`p
Fjo)FhflFioFjoFjo>Fep-Fgp6'FjoFinFgoF_oFhfl>FjpF[q>F^qF_q>FhqFiq>FhqF^r>FcrFjo>
FerFfr>FjrF[s>F^sF_s?(FPFjoFjoFPFdsC(>FhsFis>F[tFes>FerF]t>FjrFat>Fcr*&FcrFjo-F
\u6$-Fet6$/F^o,&F^oFjoF`zF\rFhs/F`zFduFjo>F^sF_s>FhuFiu>F[vF\v>F[vFbv>FfvFgv>Ff
vFiv>FdxF]w@%Faw>Ff^lFdw>Ff^lFfw>F\w-F[x6%F[vF^oFdx>Fcw-F[x6%FfvF^oFf^l@(1FdxFf
^l>Fbu,&FfxFjoFf^lF\r/Ff^l,&FdxFjoF\rFjoC$>Fiw,$*&FcwFjoF\wF\rF_y@%-Fby6$FiwFdy
>Fbu-Fgy6$Fiw,(FfxFjoFdxF\rFjoFjo>FbuF^dt2Ff^lFcct>Fbu-Fgy6$F`oF^dt>F^\lF`o@$2F
buF`oFcz@$1F`oFbuC3?(Fb[lF`oFjoFbuF\p>F^\l,&F^\lFjoFifrFjo>Fd\l,(*&F]vFjoF^\lFj
oFjo*&FjrFjo-Fet6$Fh[lF^\lFjoF\rFhuF\r>Fd\lFcgr>FdalFfgr?(Fb[lF`oFjoFdalF\p>&Fg
alF[hrF]hr?(Fb[lF`oFjoFbuF\p>&F^xF[hrFjfr?(Fb[lF`oFjoF[pF\p>&F\yF[hrFfhr>Fgal-F
jn6$FgalFf]l>F^x-Fjn6$F^xFf]l>F\y-Fjn6$F\yFf]l>F^x-F_^l6$F^xF\y>F]]l-Fet6$/F_o#
FjoFaqFgal?(FioFjoFjo-Fedm6#FcpF\p>F]]l-Fet6$/-FjdmF[^r,&*$FioFaqFjoFfqFjoF]]l>
F^x-Fc^l6$FgalF^x>Fjz<#F^x>F^\l-Fet6$F^xF^\l>Fgo-Fet6$F^xFgo@%55Fa_l/FjzFc_l/F^
\lF`oFcz-FdzF\qFPFPFP,
I(RootOf1:6$F`hoFahl6%F6%$kviGF,FPFPC&>Fep7#-Fagp6$/F\oF`oF[p>FioFc_l?(FgoFjoFj
oFcjsF\p@$3-Fby6$&FepFbalFdy2F`oF[jt>Fio-F_^l6$Fio<#F[jtFfboFPFPFP,
I%tovu:6%%#SUGF'F(6#F+FPFPC$>Fep-Fjq6%F[`oF[pFjo@%/FepFjoFczFihtFPFPFP,
I(Zeillim:Fjco6(F-F^doF_doFDF,F+FPFPC(>Fhq-Fcgn6&F\oF[pF^oF_o>FepFjdo>FioF\eo>F
go,&-F_bl6#*&-Fet6$/F[p,(F^oFjoFhflF\rFjoFjoFioFjo-Fet6$F\\uF\oFjoFjo-F_bl6#*&-
Fet6$FceoFioFjoFaeoFjoF\r?(F^qF`oFjoF_foF\p?(FjpFjoFjoF^qF\p>Fgo,&FgoFjo*&FdfoF
jo-F_bl6#-Fet6$<$/F[p,(F^oFjoFhflF\rFjpFjoFjfoF\oFjoFjo6$Fhq-F_r6#-FcvFbalFPFPF
P,
I*bdokcertc:6(FeaqF`hlFahlFchlF-FahoFi]tFPFPC&>FepF`o?(FioF`oFjoF`_pF\pC$>Fep,&
FepFjo*&-F[x6%FcpF_oFioFjo-F_bl6#*&-Fdcq6%F\oF^oFioFjoF\oF\rFjoFjo>Fep-F_rFdjs>
Fep*&FepFjo-F_bl6#*&-Fh`m6$FgflF[pFjoF\oF\rF\rFg^uFPFPFP,
I*bdokcertd:6(FeaqF`hlF(F)F-FahoFi]tFPFPC&>FepF`o?(FioF`oFjoF`_pF\pC$>Fep,&FepF
jo*&F_^uFjo-F_bl6#*&-Fet6$/F^o,&F^oFjoFioFjoF\oFjoF\oF\rFjoFjo>FepFg^u>FepFi^uF
g^uFPFPFP,
I%zeil:FPFPFPFP@)/FT""%-F^_oF_joF\jo-FdaoF_jo/FTFf_o-FiboF_joC$-Ffdl6#%Wzeil(SU
MMAND,k,n,N)~or~zeil(SUMMAND,k,n,N,MAXORDER)~orG-FW6#%Hzeil(SUMMAND,k,n,N,MAXOR
DER,param_list)GFPFPFP,
I&gzor1:6%Fg_sFchlFahlF]fsFPFPC$>FioF`o?(FepF`oFjoF^[mF\p>Fio,(FioFjo*&-Fh`m6$-
F[x6%F\oF[pFepF^oFjoFh[mFjoFjo*&F]buFjo)F[p,&FepFjoFjoFjoFjoFjoFPFPFP,
I(bdokcto:F_gsF`gsFPFPC,>FhuFin>FepFegs@$F]jrFcz>F^qF[q>FjpFjgs>FioF`o?(FgoF`oF
joF]hsF\pC$>Fio,&FioFjo*&FchsFjo-F_bl6#*&-Fet6$/F_oFe[pFhuFjoFhuF\rFjoFjo>FioF]
^p>Fhq,&-F_bl6#*&-Fet6$F_vFjpFjoFhuF\rFjoF_qF\r>FhqF`isFaisFPFPFP,
I#rf:6$Fg_s%"bGFPFPFP*&-F]o6#,(F\oFjoF[pFjoF\rFjoFjo-F]o6#,&F\oFjoF\rFjoF\rFPFP
FP,
I'celine:6%F`ho%#iiG%#jjG63%"mGF4%"lGF,%#ttG%#yyG%#zzG%#rrG%#xxG%#ssG%#zyGFbdu%
$iiiGF'F(%"rG%$zzzGFPFPCF>Fep.Fep>Fio.Fio>Fgo.Fgo>Fjp.Fjp>F[t,&*&F[pFjoF`vFjoFj
oF^oFjo>Fjr-%$seqG6$&F^eqFgjl/Fjp;F`oF[t>FjpFdfu>F]^r-Fgr6#-F_bl6#-Fcv6#-F[io6$
-F[io6$*(&F^eq6#,&*&FjpFjoF`vFjoFjoFioFjoFjo-F\o6$,&F[vFjoFioF\r,&FhsFjoFjpF\rF
jo-F\o6$F[vFhsF\r/Fjp;F`oF[p/Fio;F`oF^o>F^q-%'coeffsG6$-%(collectG6$F]^rFhsFhs>
Fhq-Fc^l6$<#F^q<#Fjr>Fhu-F_bl6#-F[io6$-F[io6$*&&F^eq6#,&*&FgoFjoF`vFjoFjoFepFjo
Fjo-Fbdl6$,&F[vFjoFepF\r,&FhsFjoFgoF\rFjo/FgoFghu/FepFihu>FjpFdfu>FioF`fu-Fecl6
#%"~GFjju-Fecl6#%8The~full~~recurrence~isGFjju>Fhu-Fgr6#-F_bl6#-Fet6$FhqFhu?(Fj
pF`oFjoF[pF\p?(FioF`oFjoF^oF\p>Fhu-F_iu6$Fhu-FbdlFahu-Fecl6$Fhu%$==0G>FcrFhu>Fg
oFbfu>FioF`fu>FepF^fu>Ffv-Fet6$Fhq-F_bl6#-Fcv6#-F[io6$-F[io6$*&-F[io6$F^ju/Fgo;
,&FioFjoFjoFjoF[pFjo-F_bl6#-Fcv6#*&-F\o6$Fdju,&FhsFjoFioF\rFjoFdhuF\rFjo/FioFgh
uFgju>Fer-F_bl6#-Fd[m6#-F_blFjvFjjuFjju-Fecl6#%7The~telescoped~form~isGFjju>F^s
-Fd[m6#-Fet6$Fhq-F[io6$*&-F_bl6#-F[io6$F^juFfjuFjo-Fbdl6$FdjuFhsFjoFgju-Fecl6$F
^s%2==G(n,k)-G(n,k-1)GFjju-Fecl6#%[owhere~G(n,k)=R(n,k)*F(n,k)~and~the~rational
~function~~R(n,k)~is~GFjjuFerFPFPFP,
I&ctold:F$F*FPFPCP@$FSFV>FgoF`o?(FioF`oFjoF[pF\p>FgoF^p>FepFfp>FjpF[q>F^qF_q>Fc
qFdq>FhqFiq>FhqF^r-Ffdl6$%*yakhas~isGFhq>FcrFjo>FerFfr>FjrF[s>F^s-%*resultantG6
%Fer-Fet6$/F^o,&F^oFjoF]^rFjoFjrF^o-Ffdl6$%(res1~isGF^s>F^eq-Fjht6$F^sF]^r-Ffdl
6$%&kv~isGF^eq?(FPFjoFjoFP2F`o-FedmF`drC)>F[t-Fgy6#-FjdmF`dr>Fhs-Fcap6$Fer-Fet6
$/F^o,&F^oFjoF[tFjoFjr>FerF]t>FjrFat>FcrFjt>F^sF_av>F^eqFjav>FhuFiu>F[vF\v>F[vF
bv>FfvFgv>FfvFiv>F\wF]w@%Faw>FcwFdw>FcwFfw>FiwFjw>F^xF_x@(Fbx>FdxFexFhxC$>F\yF]
y@%Fay>FdxFfy>FdxFiyF[z>FdxF]z>F`zF`o-Ffdl6$%&k1~isGFdx@$FbzFcz@$FgzC1?(FjzF`oF
joFdxF\p>F`zF\[l>Fb[lFc[l>Fb[lF[\l>F^\lF_\l?(FjzF`oFjoF^\lF\p>Fc\lFg\l?(FjzF`oF
joFdxF\p>F\]lF^[l?(FjzF`oFjoF[pF\p>F`]lFb]l>Fd\lFd]l>F]]lFh]l>Fa]lF[^l>F]]lF^^l
>F]]lFb^l>Ff^lFg^l>F`zFi^l>FgoF\_l@$F__lFcz>FepFc_l?(FbuF`oFjoFdxF\p>FepFh_l?(F
buF`oFjoF[pF\p>FepF_`l>F`zFe`l>FgoFh`l>FgoF[al>F_alF`al>FdalFeal>FgalFhal>FgalF
^bl>FbblF`o?(FioF`oFjoFdblF\p>FbblFgblF^clFPFPFP,
I%yafe:6&F-F)F(F\elFi]tFPFPC%>FepF`o?(FioF`oFjoF^[mF\p>Fep,&FepFjo*&Fc^tFjo-Fet
6$F^`uF_oFjoFjoFepFPFPFP
