Citation
The mechanization of the proofs of combinatorial identities

Material Information

Title:
The mechanization of the proofs of combinatorial identities
Creator:
Venter, Alexsis M
Publication Date:
Language:
English
Physical Description:
viii, 56 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Combinatorial identities ( lcsh )
Automatic theorem proving ( lcsh )
Proof theory ( lcsh )
Automatic theorem proving ( fast )
Combinatorial identities ( fast )
Proof theory ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 55-56).
General Note:
Department of Mathematical and Statistical Sciences
Statement of Responsibility:
by Alexsis M. Venter.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
71814489 ( OCLC )
ocm71814489
Classification:
LD1193.L622 2006m V46 ( lcc )

Full Text
THE MECHANIZATION OF THE PROOFS OF COMBINATORIAL
IDENTITIES
by
Alexsis M Venter
B.S.. Mathematics
Wheaton College
2001
A thesis submitted to the'
University of Colorado at Denver
and Health Sciences Center
in partial fulfillment
of the requirements for the1 degree of
Master of Science
Applied Mathematics
2000


This thesis for the Master of Science
degree by
Alexsis M Venter
has been approved
bv
[
Date


Venter. Alexsis M (M.S.. Applied AI a 11 k 'i n a I ics)
The Mechanization of tin* Proofs of Combinatorial Identities
Thesis (liix'ctc'd by Professor Bill Cherowitzo
ABSTRACT
For hypergeometrie sums. the transition has been made from hand written
proofs to mechanized computer proofs. The noil-mechanized algorithm of Sister
Mary Celine Faseninyer led to a foundational theorem stating that any proper
hypergeometrie sum satisfies a recurrence relation of the form
i .1
EE a,.,{n)F{n j. k i) = 0.
;=o ./=()
Gosper's algorithm (for indefinite sums) and the Zeilberger-Petkovsek algorithm
(for definite sums) art* mechanized procedures for finding such recurrences and
subsequently stating the closed form representation of the original sum. These
algorithms together give a complete solution to the question of whet her a sum of
proper hypergeometrie terms can be written in "closed form." They will either
find the desired identity or let you know that the sum cannot be represented
in such a way. Moreover, the \\ Z algorithm provides a certificate which can be
used for manual verification.
This abstract accurately represents the content of the candidate's thesis. I
iii


I
[
i
|
IV


DEDICATION
This thesis is dedicated first and foremost to my husband.
. Jaco Venter, and also to
mv family:
Byron A Donna Chapin
Koos A Louisa Venter
Albert PreMon
Gwen .lansM'ii
Orpa Aylward
Chapins. Prestons. Gardners.
Janssens. Venters, and Camphors
and all my former math teachers at:
Francis Howell North High School. St. Charles. Missouri
Wheaton College. Wheaton. Illinois
Fniversit v of Colorado. Denver. Colorado


ACKNOWLEDGMENT
This thesis would not have been possible without the encouragement and guid-
ance of Bill C'herowit/.o. to whom I am extremely grateful.


CONTENTS
1. Introduction..............................
2. Preliminaries ..........................
2.1 Generating Functions....................
2.2 Hypergeometric Sums ....................
2.2 Cain mica I Forms.......................
2.4 Resultants..............................
2.5 Closed Form.............................
4. Past Methods.............................
4.1 The Snake Oil Met hod...................
4.2 The Hypergeometric Database.............
4.4 Sister Mary Celine Fasenmyer's Algorithm
4.4 Brief Analysis of Mary Celine's Algorithm
4. Gospers Algorithm........................
4.1 The Algorithm ..........................
4.2 Example's of Gosper's Algorithm ........
4.4 Analysis of Gosper's Algorithm..........
5. Zeilberger's Algorithm....................
5.1 The Algorithm...........................
5.2 An example of Zeilberger's Algorithm . .
5.4 Analysis of Zeilberger's algorithm......


(j. \\ / Algorit Inn................................................. 10
(3.1 Tlu' Algorithm ................................................. 40
(3.2 An Example of I Ik1 WZ Algorit Inn ............................ 44
(3.3 Analysis of the \VX Algorithm................................... 43
7. Algorithm "Hyper"............................................... 47
7.1 "Poly.......................................................... 47
7.2 "Hyper......................................................... 40
7.3 Examples Using Algorithms Poly and Ilyper....................... 40
S. Summary ........................................................ 44
References......................................................... 4 4
viii


1. Introduction
Over tin' past century, the degree to which computers art' involved in the
world around us has increased explosively. Now we art' not only finding' more
ways to make use of them, but also smarter ways. Computer programming
together with mathematical algorithms has saved much time and energy in per-
forming mathematical computations. In other fields as well, we are learning to
delegate more tasks to the computer, and in eliect pushing our cognitive skills
out of their comfort zone's and into new realms.
One instance' of this ever more common phenomenon is 1 lie use' of eomput-
e'rs in finding identities ol e'ombinatorial sums. Through recent history, many
mat heinat ieians have1 spent much time solving individual ielent it i they found particular interest or relevance. And the' noeel for these identities
will continue to be of great importance. As solving these identities could seem
an infinite project, a sharp algorithm or any sort of proce'dure for minimizing
the task would hi' highly valued. Mathematicians have formed methods and
algorithms for specific classes of sums to minimize t ho work. And recently, algo-
rithms have berm developed and refined to do this automatically by computer.
Aiilonwh (I Ihroran prornif]. or ATR is the proving of mathematical theo-
rems by a computer program. Depending on thr' underlying logic, the problem
of deciding the validity of a theorem varies from trivial to impossible. A related
problem is proof r< rification. where an (existing proof for a theorem is certified
valid. For this, it is generally required that each individual proof step can be


verified by a primitive recursive' runcliou or program, and lienee' llio problem
is always decidable. Inlcmrlin lluorcm proncr* require a human user lo give5
hints to the system. Depeaieling on the degree of automation, the prover can
essentially be' re'duce'd to a ])rool che'cke'r. with the use'r ])roviding the' proof in
a formal way. or significant proof tasks can be performe'd automatically. Inter-
active prove'rs are' list'd for a varie'ty of tasks, but ('veil fully automatic systems
have by now proven a munbe'r of inte're'sting and hard the'ore'ins. including some
that have eluded human mathematicians for a long time. Howenot'. these suc-
ce'sses are sporadic. and work on hard problems usually requires a proficient user.
A computc.r-assistul proof is a mathematical proof that has be'on generated by
computer [18].
There is much to benefit from this transition of hand worked proofs to com-
puter solutions. This paper will give' a survey of the past and current, methods
and algorithms for combinatorial identitie's and wlieae we' stand in the' solution
of these problems.


2. Preliminaries
2.1 Generating Functions
A basic knowledge of generating functions is required for understanding the
Snake Oil Method in Section 3.1
A generating function is a formal power series
whose coefficients give the sequence . ..} 13].
2.2 Hypergeometric Sums
A hypergeometric series ]Tt. (k is a series for which / 1 and the consecutive
whore P(k) and Q{k) are polynomial functions.
In plain terms, for further illumination, a hyporgeoinetric sum will have' a
summand including only factorials, polynomials, and exponential functions of
the summation variable.
Example 1. bet
/a) = £
term ratio is a rational function of the summation index k [14].
Another wav of viewing this is that
Pik)
h Qik)
Then t{)
i ri
Mi -
>0
1. and the consecutive term ratio is
nlk\(n k)\ n k
oH-ip
() 3(b-!)!(-/r
1 )!(-//- 1)!/)! 3(b-l)'


when1 clearly the numerator and denominator are hotli rational fmictions of k.
Example 2. Let
where there is no dear simplification, and neither the numerator or denominator
is a rat ional function of k.
2.3 Canonical Forms
A canonical form is a clear-cut way of describing every object in a class in
a one-to-one maimer do]. A canonical form is required to have two essential
properties. Every object under consideration must have exactly one canonical
form, and two objects that have tlit' same canonical form must be essentially tilt'
same [lb]. Then to verify that some entity .1 is equal to an entity B. you must
just check to see that the canonical form of d is equal to the' canonical form of
Write' eae-li polynomial in ordeT ol eh'sce-neliny powers for your canonical lorm
and you ge't
k
Tlie'ii Li = (> and the' consee-utive' te'rm ratio is
B.
Example 3. Verilv that 3(.r lj2 !J.r = 3( lti .r + .r2 l.r).
3(.r2 8.r Hi) + U.r 43 3.r o.r2 12.r.
3.r2 2 l.r -43 9.r = 13- lo.r 3.r2.
3.i2 lo.r 13 = 3 1 o.r T 13.


For a. common, non-mat hemal ical example, a Social .Security Number would
(ideally) be a good canonical form to verify that two statements regarding a F.S.
Citizen refer to the same person.
2.4 Resultants
In step 2 of Gosper's Algorithm, we need the idem of the Resultant of two
polynomials. Given p and q. two polynomials which factor into linear factors
p{x) = a0{x - G )U' - r-2) U i'm)
q(x) = bt){x - )(.r - s2) (x s).
the resultant is
tit II
H(,p(x).q[x)) = a;^llll[rl-^).
,=\ ;,=l
Example 4. L('t p(x) = [x h)2 and q{x) = 4(.r + 2)(.r 7)(.r o). Them
o --- 1. b{) 4. tv = 2. n = 4 and n h. r2 = h. s, = 2. so = 7.= o. Then
the Resultant of p and q is
2 a
/?((.) h)2. 4(.r -p 2)(.r 7)(x + o)) = 1;14 JJ s.,).
j=i
Rip.q) = Hi [(// + 2)(7i 7){h + 5)(/; A 2)(h 7)(// o)j.
R{p.q) = l()(h + 2)2(h 7)2(h o)2.
An alternative procedure is given by Sylvester [if for a situation in which
the polynomials do not factor completely into linear terms. Let tin1 polynomials.
p and q. be written in the following manner
m
p(.r) = YJ"l-rw-i
> = \)
)


<]U) = ^ bi.r"
?=i)
Then the resultant ran be expressed by the following m + n ln-
do 1 a-2 . dm 0 . .. 0
0 do i d,-1 d,n .. 0
0 0 dm
bo bi b2 . bn 0 . . 0
0 bo h bn i b . 0
0 0 b
Example 5. In the previous example. consider how \v<
t ('rminant if t h(' ].)olynoinials W( to unf vet ored:
q(.v) = l.r:! - 1 oti.r 280.
1 - -2 h h1 0 0
0 1 -21, Jr 0
0 0 1 2lt Ir
1 0 1-3G -280 0
0 1 0 -150 - 280
The above determinant is 10// i 12 18/;1 - 2210// a ^
which is equivalent to the factored Ibrni lG(/t 2)2(h 7)2(
w n detenninant:
would tisr1 the de-
- 2h.v + fr and
- 87800// + 78 100
b 5j2.
(i


2.5 Closed Form
Definition 2.1 For our purposes in deuiliny irith he/pe repometi'ic term* and
sums. a function f(n) cun be theruyht of us heiny in closed form if it i.s eejued
to a linear combination of a find numbe r, sup r. of hype rye onn tree terms. The
numbe r r must be' an absolute constant, i.c.. it must be hide pe:neb at of all curi-
ablc.s and puramete rs of the problem.
<


3. Past Methods
Many methods have been developed to take care of eertain classes of sums.
Many of these are clever and quite helpful, but also now obsolete1.
3.1 The Snake Oil Method
One slick procedure1 is the1 Snake1 Oil me1!hod. The ielea here1 is to use gen-
erating' functions to find whole1 classers of Mims and pluck the1 sum in epmstion
from the1 e-enffie-iemts eif the1 generating lime-tion. The1 stnps from Will j71 are as
follows:
1. Identify the1 free variable1, say n. that the1 sum ele'pe'nels on. Clive: a name1
to the1 sum that you arc1 working on: call it f(11).
2. Let F{x) lx1 the ordinary power- seric's generating function (opsgf ) whose1
[:r"] is /(//). the1 sum that youd love1 to evaluate1. The1 notation denote's
the1 coe'fficient of.;'" in any generating lunction. In this seating, basically
we> have1.
FU) '= ^2f(n)x".
n
3. Multiply the1 sum by r" anel sum o\rer n. Your generating function is now
expinsseel as a double1 sum. ewer n anel oxer' wlia.1 ewer variable1 was flirt
used as a dummy summation variable.
4. Interchange1 the1 e>rd and e'xprers the1 inner' one1 in simple1 closed form. Peer this purpose1 it will
8


b(' helpful I o have a cal alogue of series whose sums arc known, such as llm
list in sect ion 2.d of 7j.
j. Try (o identity the coefficients of the generat iug function of tin' answer,
because those coefficients are what you want to find.
Example 6. Esc the' Snake Oil method to find a closed form representation for
For step 1. we note that the free variable is n and k is the dummy variable.
Then Fix) = f{n)-r" is the generating function with which wo are con-
cerned.
Proceeding with the method, we multiply by r" and sum over n.
Next we interchange the summations and express the inner sum in closed
form. This is the step in which we need a catalogin' or listing of series whose
sums are known. This is a significant downfall of the Snake Oil met hod.
(n = 0. 1.2. . .) .
9


Now ](>l lii-k and wo lmvo a convenient conversion lor tho inner sum.
ru) = '52jJ''Y,
.V
k- >n
F(r) = ^V(l +./)*'.
FU) = ^(.rw ,r)A .
*>()
Then, via knowledge of generating functions. we know that
F(x) ----------- = ----------
1 7 1 -(,c + .r-) 1 d
d his general ing function is known to generate tlie Fibonacci numbers giving
fin) = F where /'_] = 0. /T = 1. b\ = 1. Ft = 2. F:i = 3. F\ 5. 6/c.
E
oo
k
n k
= F
>i = 0.1.2....).
closed form wo have for Fn is an approximation.
n 1
F
*5 1
0
Many sums that an' commonly solved with the Snake Oil method art' liy-
pergoometric suns. From this point forward, we consider methods dealing only
with hypergeometrie sums.
11)


3.2 The Hypcrgcomctric Database
As previously mentioned. much tilin' has been spent on solving individual
sums. One problem with this is that much rime can be spent solving equivalent
Mims which an' disguised to look differently. A step toward eliminating this
problem is the formation of a canonical form for hypergeometrie sums. Any
hypergeometric sum can be converted into this canonical form, and then we can
"look it up" in the hypergeometric database.
1. Given a series Xu-G- Shift the summation index k so that the sum starts
at k = 0 with a nonzero term. Extract tIn' term corresponding to k 0
as a common factor so that the first term of the sum will he 1.
2. Simplify tin' ratio to bring it into the form when* P.O art' poly-
nomials. If this cannot be doin', the .series is not hypergoonietric.
3. Completely factor the polynomials P and () into linear factors, and write
tin' term ratio in the form
P(k) (k Q[k) (k b))(/.' + bo)... Ik b,t j(k 1)
If tin' factor k 1 in l la* denominator wasn't then', put it in. and compen-
sate by inserting an extra lad or ol k-r 1 in the numerator. Notice that all
of tin' coefficients of k. in numerator and denominator, are 1. \\ hat ever
numerical factors are needed to achieve this are absorbed into the factor
.r.
11


I. You liavr now ideal ified the input series. It is the common factor that you
extracted in stop 1 above, multiplied by tlu' hyperyeomet ric series which
is defined be:
i a 2 ur
b ) b,t
Example 7. Use tin' Hyperyeoinetric Database look up method to find a
closed form representation of tlit' sum
\Yo already know the closed form for this sum. but we will use this simple
example to illustrate' the method.
For step 1. note' that when k = 0. the summand is nonzero. Also, the term
correspondin';' to k 0 is 1. >o we need not (extract anything.
The consecutive term ratio is
\Yo now look up ii7!) in our small list of identifies in chapter > of \i] and find
bet tins; a = n and ~ .r
ti,
Thus we have'
it


/?
lid
x
(1 + .rj-
= (l+.f
(')e'arlv a. huge' drawback is that wr must reference some list or database of
known identities. There may be any number of partial lists: you can create
oik' for yourself easily. The problem is that no comprehensive hypergeometlie
database exists as the number of possible identities is infinite.
3.3 Sister Mary Celine Fasenmyens Algorithm
We now consider an algorithm which unlike the previous two methods is
free of dependence on lists and catalogues of known identities.
We are given a sum. f(n) = Ylh ^'{n- A1). where F is doubly hvpergeometric.
That is to sav both the ratio. b *?! end the ratio b~--1 f? are hvpergeomet-
lie. Ultimately, we are looking for a recurrence formula lor the sum. f[n). and
wo start by finding a recurrence for the summand. F(n.k). Our recurrence for
the summand will bo in the form
l ./
Y Y, O./UOTW j- k i) 0- (3.1)
<=o j=D
Tin1 steps of th(> algorithm are as follows.
1. Fix trial values of / and J. say I J 1.
2. Assume the recurrence formula in the form of (3.1) with the coefficients
oij(n) to he determined, if possible'.
3. Divide* each team erf (3.1) by F(n.k) and lvdue-e e'acli ratio n by
simplifying I he' ra tiers erf l he1 fae terrials that it e-out a ins. so t hat emly rat ional
fund ions of n and k remain.
O
o


1. Place1 the cut in1 expression over a single commoii denominator. Then
collect the numerator as a polynomial in k.
a. Solve the system of linear equations that results from equating to zero
the coefficients of each power of k in the numerator polynomial, for the
unknown coefficients of a, r If the system has no solution, try the whole1
tiling again with larger value's of I and/or ./. That is. look for a bigger
recurrence.
G. Once the recurrence for F[n.k) has been determined, sum said recurremce
over k and work with the1 result to find the recurrence for the sum. f(n).
Example 8. Ise Sister Coline's algorithm to find a closed form of the sum
Again, it is no challenge to find this sum we know its closed lonn by heart.
We will use I his simple sum to demonstrate t he steps of Mary Celine's algorithm.
all0{ii)F{v. k)+aUA{n)F{n-l. k) t rq.0( )/'( k-l)-aLL(n)F(n-l.k-l) = 0.
C'liangi1 notation so that the coefficients are most simple and dont need sub-
scripts. Remember that they do still depend on n.
aF{n. k) + bF(n 1. k) + cF(n. k l) dF{n 1. k 1) = 0. (1G)
Lot / = J
(12)
/ = !) /= II
1 I


ill , (n-
a ----------- + b
ill
d-
In 1)!
kiln k)\ k\{n 1 A-)! (k 1)!( k 1)! (k l)l(n k)\
Now divide through by F(n.k) = jj~zj~i-
nlkl(n k)! , (n 1 )!/,!(// A-)!
II-----:-----------:--------b-
ulkl(n k
(n-miln-k)l (
<1 --:---. = ().
k\(n-ky.nl kl(n 1 /,)!;(! (k 1)!(n k 1 )lnl (k l)l(n k)lnl
An- l)!(u A)!
a b-------;- c
k\(n k)l
An 1 )!/,!
d----------------^ = 0.
n-l-k)ln\ (k-\)\(n-k + 1)! (k-\)ln\
, /v k k
a b--------------------(-
A =,,
n n k -f 1 n
Next, find a common denominator and collect terms in the numerator as a
polynomial in k.
n(n k -r 1) (n k)( n k + 1)
a:----:-------b-------------------L (
nk
k(n k + 1)
a----------- (J.
n(n k + 1) n{n k -\- 1) n(n k f 1) n(ri k 1)
an(n k + 1) + b(n k)(ri k + 1) enk dk(n k 1)
ll( ll k h 1)
k2(b d) k(rm 2bn h cn dn cl) ion2 + cm bn2 bn)
n (n k -g 1)
Thus we have the following system of equations
h cl = 0
-cm '2bn b cn dn d - 0
cm2 cm + bn2 bn --- 0
(T4)
which yit'ld the solution sot <7( 1. 1.0. 1).
Ise cl = 1 and equation (TO) to obtain the resulting recurrence for F(n.k):
F(n. k) + Fin 1. k) + Flit l. k 1) = 0.
Fln.k) F(n 1. k) + F( n 1 1).


(Note that this recurrence is what wo would expect to find based on Pascals
Triangle.)
Now sum this rocurronco over all integer values of k. If k < 0 or k > n. the
summand F(n.k) will vanish and so the sums contain only finite numbers of
tonus. We get t hat
7: F{n. k) = F(n 1. k) F{n 1. k 1).
k k k
f(n) = /(/?- 1) f(n 1).
fin) 2f(n 1).
Using some small eompub'd values [/(()) = 1. /(1) = 2./(2) = 4 and our sim-
plified recurrence, wo determine that
f(n) = 2".
3.4 Brief Analysis of Mary Celines Algorithm
Although Sister Celine's method has been much improved upon, it retains
its importance as being one of the first results regarding computerized proofs of
identities. Also, her algorithm led to a general existence theorem for hypergoo-
motric sums' recurrence relations which we will now slate.
Definition 3.1 A function Fin.k) is said to lx a proper hyper-geometric
term if it can lx irriltcn in tin form
F(n. k) = P(ii.k)
YlZMl'n-l)'k 1 c)i *.
- r'k 1
in which x is an indeterminate orcr. sat/, tin complr.r ntnnlxrs. and
Hi


I. P is a polgnoniini
.2. the a. s. b 's. u '.s. c '.s tire spieifie integers, that is to sag. tin g ho not contain
ant) additional parann tees. and
o, the tpiantitn.s an and re are finite, nonnegatiri. specific inti t/i rsf'/l.
Theorem 3.2 Lei F(n.k) h< a prop< r hgpi rgeonielrie term. Thin F satisjiis a
k-free renirri nee relation. That is to sag. thin exist pos/tire integers I.J. and
polgnoinials for i 0.....F. j = 0........7. not all i< ro. such that the
n careen ce
i .i
^ y, a,,j{n )F{n j. k i) (I.
(3.7)
; = () / = !)
holds at enrg point (n.k) at which F(n.k) 0 and all of tin. rallies of F that
occur in (!.?) are well definitl. Fnrthcnnon then is such a rccurrtncc with
(/./) (/. /*j win n
j' = 1b' i ~ 1i: r = 1 - i + 1 '< I) -1 j
This theorem guarantees that Sister Celine's algorithm will succeed il / and
J are large enough. It also provides specific values Cor which the algorithm will
work. These values. F and ./'. an' not necessarily the smallest such values that
will work.
Proof: A lengthy proof of the first part of this theorem is given by Will
and Zeilberger in [12]. Before beginning tin' proof, preliminary work is done to
wnt(' tlie generic ratio. as
/! II. AI
F[nj.k i) e(n.k)
Fin. k)
Sin.k)
.8)
17


where r(n.k) equals
P(n
ii u
j. /> /) pp rf(\aj + * a-n m*+r.-) pp
-=i .=1
/ />_ / <'0 u / r.
.ff(ll*j ~~ 'V- ,l*n + /'*/>' + U\)-
;0
and <5(n. A') ('(pials
mi rr
P(n.k).v' f b*i .n^n hj: + rs) rf{Ui^j + r./ //..,/> + /\,/r 4- u\s).
s_l t
n i i i.) The notation lor rising factorial and tallinir, factorial a.re as follows: rf(.r.y) =
n :>'/ ./ and jj(x.y) = J] -i\(y~j)- All other notation is as in Definition
3.1. To begin. assume the recurrence (3.7). and try to solve for the coefficients,
by first dividing through l>y F(n.k). Then we have
E
:--- = 0.
Sjj (n. k)
Next a coninion denominator is found to divide
(3.9)
P( // ./-) f f \ -=) S=J
when1 x+ = max(.r.O). The fractions art' then cleared out by multiplying (3.9)
through by (3.10). We gel
E (li.j(n)i'i.j(n.k) = 0. (3.11)
' djAn.k)
a polynomial in k. where A is the common denominator (3.10). Finally the
coefficients of each power of k inf3.11) art' equated to zero. In order to validate
this theorem, we must verily that the system of linear equations resulting from
(3.11) has a nontrivial solution. Due to the properties ol rising and tailing
fact orials. the degree of k grows linearly wit h / and J. The number ot unknowns.
a, r grows similarly to / J (it is act ually (/ T 1)(J + 1)). I hen when / and J art'
18


sufficiently large. the number of unknowns will surpass the number of equal ions
in our system, and we will be guaranteed a nontrivial solution. An additional
proof is omitted that, guarantees /* and .J" an1 satisfactorily large values.
The statement of this theorem is foundational to tin' mechanized proofs we
consider next. It is strong it says we can find a recurrence relation for any
proper liypergeometrie term. The algorithms we consider next give specific steps
for finding this recurrence and then for finding a closed form representation from
the recurrence.
H)


4. Gosper's Algorithm
Gosper's algorithm is of great importance in the computerization of closed
form summation problems. Not only dot's it completely solve what it sets out to
do. but Gosper's algorithm plays a foundational role in both Zeilberger's C 're-
al ive Telescoping algorithm and tlit' \YZ algorithm. Gosper's algorithm answers
the following question: Given a liyporgeometlie term /.. is there a. hypergeo-
metric term such that z /?
If Gosper's algorithm succeeds, then we know that the sum of the hypergeo-
metric term can be written as another hypergeometric term, plus some constant.
If Gosper's algorithm fails, then we know that the sum cannot be written as a
liyporgeomet ric term plus a constant, nor can it be written as a linear combi-
nation of a fixed number of hypergeomet ric terms. (It cannot be written in our
closed form.)
4.1 The Algorithm
Suppose wo are given a sum
(i-i
s = Xa
k-\S
whore G G a hypergeometrio term. If we could express G- as the difference of
two hypergeomet ric terms.
G = -'(+! ~ -a- ('i 1)
20


then \v( arc led to a simple looking relationsliip.
a-1
+ /- 1 = -r /_1 = . r'o + G = + ~o-
l.=\)
where Co is some constant.
Given a hypergeomotlie t('rm. IGosper's algorithm will either product' the
desired term c (and we say that / is Gosper-summablo) or verily that no such
hvprrgromrt ric exists.
If c is a hvpergeometl ie term satisfying ( 1.1). thoii f1- is a rational function
' n
of ii. Call this unknown function y(n) and rewrite as = //(//)/,,. Substitute
this value of into (4.1) and we got
r(it)uln -r 1) ij(n) =
1.
whi're /(//) = Now we have shifted iht' problem from finding hypergeomet-
ric solutions of ( 1.1) to finding rational solutions of ( 1.2). a linear recurrence.
Next, tin' problem is again shifted into finding polynomial solutions of another
linear recurrence. Assume that r(ii) can bo factored in the following way:
a(n) c(n + 1)
bin) c(r>)
when1 a(n).b{n). and c{n) are polynomials in n. and
(1.3)
gedbdn). b{n + h)) = 1.
(4.1)
for all nonnegative integers h. Gosper tells us to look for a solution of ( 1.2) in
tin' form
t/( //) =
b{n 1 ).r( n )
<{n)
(1.4)
21


Notice that now we have a represent at ion for . which wc now turn our attention. Subslitut ing (4..4) and (4.5) into (4.2) we get
that ./(;?) will satisfy
a(n).r(n 1) b(n 1 ).r( n) = c(n
(4.(4)
Gosper did prove a t heorem t hat guaraniees ,r( n ) is a polynomial in n [3 From
this point. w< iK'ed only to find .r{n) and then, substituting again, ret uni the
value
b(n 1 ).rin)
^00
in.
Obviously there an' many details to consider in addition to this
relevant equations. The main computational aspects of Gosper ^
be divided into the following four steps and many substeps.
(4.7)
general flow of
algorithm can
I. Form the ratio /(??) = 1 from the given Ilypergoonietric term. t. rin)
is a rational function of n.
2. Writi' r(n) ^ j1 where a(n).b{n). c[n) an1 polynomials satisfying
(1.4).
At times it may seem that we can just easily spot the appropriate values
for a(n). bin), and c(n). However then' are specific detailed guidelines that
must be followed in order to correctly proceed.
Let J{n) be the numerator of /(//). and let g(n) be the denominator ol
r(n). If gcd(/(ii). g(n It)) 1 for all nonnegative integers h. we can take
a(n) = f[n). bln) = gin), and c{n) 1 for our factorization ol r(n). II
not. we must "factor out" the common piece by lollowing thesi1 steps:
99


(a) Lot r{u) = ^7777 "'here / and mials. and Z is a consl ant:
(1>) Lot R(h) bn assigned the value of Hanillanl(f(n).y(n 4- /;)).
(c) Let S = {/?i. ho....../?.v} 1h tlie set of nomiegafive inr('g R(h) (X > ().() < In < h2 < ... < hy) .
(d) Let /;,,(/?) = /(??) and r/n(n) = //(/?). For j = 1.2....V perform the
following loop:
i. Assign to Sj(n) the value of gcd(/p_i (n). ii. Assign to pAu) the value of v 1
iii. Assign to q,{n) tin' value of y,n 11"'.
((') Lot a{n) = Zpy(n). b(n) = qy(n). and c(n) = ri)=i II/=i *'(T> ~ j)-
\. Find a nonzero polynomial solution of .<(//) of ( 1.0). if one exists: ol herwise
n't urn X];,'=u G ail(l st ()P-
St<']> 3 consists of two main parts. First, yon find an upper bound on the
degree of ,*(//) via Gosper's algorithm and second, you find the polyno-
mial x(n) which satisfies (1.0) above using the method of undetermined
coefficients. Before listing the steps, we introduce souk* notation and ter-
minology. Let deg (/(/;) bo the degree of polynomial a(n). Let Ic a(n) be
the' loading coefficient of a{n). Let A be the coefficient of the term of de-
gree [deg a(n) 1] in (/(/() bet R be the coefficient of the term of degree
[deg b(n 1 ) 1] in b(n 1).
23


II deg a(n) (l(\u, b{n) or lc a(n) / lc b(n) (lion
I) = {deg c(n) max {< It '.Li, a(n). dog />()}}
(1>) If dog rd.) = dog />() a ]u\ lc a(n) = lc b{n) I lion
I) 1 [ 1c a(n)
(o) Based on tin' above two rases. I) will contain either one or two el-
ements. Now remove any elements from I) that an' not positive
integers or zero. If D is now empty, return "no nonzero polynomial
solution" and stop. Otherwise' the upper bound for tin' degree of.?(/?)
is the maximum element in D.
(d) I se the method of undetermined coefficients to find a nonzero poly-
nomial solution .r(n) of (f.ti). If none exists, return "no nonzero
polynomial solution" and slop.
4. Return zn and stop. Step 4 is quite straightforward now
that we have' found x(n).
Note that if our sum is not Gosper-summable. the' problem will occur at step
4. i.e.. we will not bo able io find the desired polynomial .?'(//.). If the sum is
Gospor-siimniablo. I hen once we find we easily hart y, = ;n. If the
lower bound is some ry ratlin' than zero, that is no problem, wo simply pint
-71 -Or


4.2 Examples of Gosper's Algorithm
Example 9. 1'se Gosper's algorithm to find a closed form representation of
the sum

E
n=()
n4r
TG
Step 1 is (juife simple' and straight forward. We form r[n) = and simplify
' n
with algebra.
(. + l)4 !"-1^') = ( + 1) - l)2 = -(>> ~ 1)
ri4(2n 2)(2n + 1) u4(2 1)
Step 2 requires that we write r(n) in the form of (4.4) above. In this example,
it might seem that a good idea would be to take* n[n) -- 2(n 1). bin) = 2n 1
and c(n) = n4. Wdiaf we would bo missing is the fact that both the numerator
and denominator. / and g. must be moiiie polynomials. Thus wo are not quire
finished reducing rin).
r(n) =
(ii 1 )'
/*:1 (II y ) '
Xow consider gcd(/(n). g(n /?)). Wo would like to know if this god is equal to
1 for all nonnegative integers h. If so. wo would have our simple factorization
and move1 on to stop 4. However, a quick counterexample of h = 1 shows that
the god is not alwavs 1. If h 1. then
1 *)
ged(( n + 1(n + h)l(n + It - ged((u 1 );I. (it + 1)1 (// -)) = (n 1 ) .
So W(' must follow the extended rules for stop 2.
'i'") T'': 'ii M) ^ /(") = + l) - and g(n) n4(n f- ^).
23


Wo must find R{h). tin Resultant off{n) an cl <]{u + h). Using t ho met hod
provided in thr* preliminaries. R(h) = (h ])2l)(h 4);|.
.s' = {1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1. 1} and |T| = 20 = .V.
Let Pula) = [a l)'1 and (/,,(/)) = //'(/; -f 4). For j 1.2.........................20 perform
the loop to assign values to sp(//). Pj(it). and s'i(n) = In l)1 pl(ii) u~ 1 + h
S2(n) l p.,(u) It 1 (/;(//) II +
*;\{n) = 1 /).;(/t) = // 1 = II ~T \
sgnUO = 1 p-2u(n) = I) + 1 Chain) = n ^
This loop gives the final results we need to determine that u(n) = n + 1.
b{n) = n -f. and (in) r/4.
Now we know the Firm of the equation that wo must use to find .r(n).
(n + 1 ).;(// !) (//
1
o
).r( n) n'.
Before looking at the direct ions for step .'j. we note the following: deg a(n) =
deg b(n) 1. Ic a(n) Ic b(n) 1. -4 1. and B 4. Step 3.a. does not
hold, so 3.1). dot's. Thus
I)
-i.Td
1
-1
Wln'n we rctmivc tht' numbers that art' not positive integers or zero, what we
have left is the integer 4. This will bo our cl. tin' upper bound on the degree' of


j-(n). Xow use th(' method of undetermined coefficients and solve the following
('(|uat ion.
(/> ^ Dfco -f cL(n 1) c2(n + 1)J cAl/i + 1) o4(/; 4- 1)')
-( ^)(r + ciu + c-2ir c-An* r.p/4) = 4.
l/sinff Derive 0 for computation.
) 40 , 40 52 4
x{n) n 1 if -f- _ >r 11 -
11 09 231 093 231
Step 4 is to : teturn the value 1 of _ bin- -1 hri n f //) / which in our ease is
(n - 41" fin)
- n i (-;:)
We leave . c(n) unexpanded for now. G()S[)i ('fs < iltit hm has succeeded
claimed it would . All I hat is left for us i t o do is to use to find our actual
Since \v< want the sum of m -i- 1 tc'nns. we "el S,,, -s,+1 = :
(//? 4- (I) r;)4U
.S'... = ---------------^4-------------------x(m + 1)------------------------------------------,r(0).
r2""2)
\ iK + i)
0
S',,, =
(tv + ) 1
1 1
/2,,,+lA -Xl' ~ 4 + o'r(U)-
,, -2(2/77 1)4"' 2
6, = ---------... ,.,.----.r(nt 1)-------------
111 /2m + 2\ ' 9j-|
V m 1 /
S,
2(2/77 4-1)1
I 2in -
2m'2,ii+I |[,2m)! 4 ^ )>
I m- 1 )-nil2
s,
.. 1"'( 7 77 + 1 ) , , 2
Sm ----To\~~;V( tv -pi) ------.
(2"') 231
2( i'")( 777 1 ) ((>3/77 1 + 112///:t + 1.S//7- 22/77 + 3)
(S)m
2
44
as it
sum.
27


Example 10. Use Gosper's algorithm to find a closed form representation of
l he sum
in C-n\~
s' = LtJ.
-^(77+ 1)4-"'
II-0
111 Slop 1 \vt' form r(n) = t-I~ and simplify with algebra. r(n) equals
(2n+?)\" ~ 1) l2" = (277 + 2)2C2n l)2 = (277 -r l)2 _ (n + ?)2
(2)|')2(/7 + 2)4-'-- 10(7? + 1):!( + 2) 4(/?+ !)(??. +2) (?? + 1)(?? + 2)'
Ste'p 2 mjuire's that we1 write1 r(n) in the form of ( 1.4) above1. Now consider
gcel(/(?7). g[n + /;)). We would like1 to know if this god is equal to 1 for all
nonnegative integers h. If so. we w<.mld have1 our simple1 factorization and mejve
on te> stop 3.
gcd((/? ^)2. (/( + h + l)(?i h + 2)) = 1.
Since1 the1 god is 1 for all positive1 inte'gvrs h wv lwe'd not follow the1 e'xtende'd
procedure1 for ste'p 2. We simply have1 a(n) = /(??). b(n) = (/(??). anel c(n) = 1. If
it is too elifficult to verify that the geel is 1. simply continue1 with the1 e'xtemded
algorithm of ste'p 2. You will come1 to the1 same1 re'sult. We now have a{n) =
(it \ )'2. b(n) (?? 1)(7? -r 2). and r(n) ~ 1.
Now we know the1 form of the1 ('([nation that we must use1 to find ,r(n).
(/? + ^)2.r( 1) 77(77 1 ).r(??) = 1.
Before1 looking at the directions for steq) 3. we1 note the1 following: de'g a(n) =
deg b(n) 2. lc a(n) = Ic b(n) = 1. .4 = 1. and H = 1. Sit1]) 3.a. doe's not hold,
so 3.b. doe's. Thus
J)= |o-2+l.^| = {-1.0}.
2S


Winll wo remove llii 111 iiiilj('is dial arr not positive integers or zero. what wo
have loft, is tlm integer 0. So the degree of.)(;?) is /.oro tho function will bo a
constant function. Now uso the method of mulctonuinod coofficiont.s and solve
t ho following e (n ^)2(rn) n(n + 1 )(r0) = 1.
c\)[ir + n 7) cn(/r n) 1.
J'lii) = Co = I.
Step 4 is to rot urn tlu value of = bt" / 1" 1 / whi
our case is
_pr
: in-in-" -i
2n 1
Again Gospi'r's algorithm returns the value of as we had hoped. Since
we want t ho stun ol w -f- 1 terms, we use .S',,.
Sn, =
c' + ep;';,-')2 i>()'
I2ra4 1
41
=
+ ]Hn+;)
S',
P-III + I
(m 1 )C2w + 2f(-2m 1)2C,
I 2r"+l(m + 1)
1


4.3 Analysis of Gosper's Algorithm
Many of the details of Gosper's algorithm took some work to prove as true.
We now examine some of the foundational proofs that allow us to move forward
at different steps in the algorithm.
Theorem 4.1 Let a(n). h(n). c(n) he polynomials in n such that (f.f) hold*.
If r(n) i. s a rational function of n sati.sfyiny (f.(>'). then x{n) is a polynomial in
n.
This theorem is needed to guarant ee that the solul ion wo find for .r(/?) in st op
3 is in fact a polynomial solution. A proof by contradiction was given by Clospor
in 1978. Lor .r[n) = ^U-j. Suppose that fjln) is a non-constant polynomial.
Multiply through (4.0) by fj(n)ij(n + 1). and consider a ?/(/?). a non-constant
irreducible common divisor of pin) and is found to divide both n{n) and h(n 4- A ). which is a contradiction of (4.4).
Proposition 4.2 Lit 0 < k < i.j < X.h G U {()} anil h < /?/,.+1. Thin
gcd( pdnj.qfn /?)) = 1.
T his verifit's that the pfs and qfs in step 2 of Gosper s algorithm have no
common factor. Therefore n(n) and h(n) (from the end of step 2) will also have
no common factor.
Theorem 4.3 Let I\ hi a fit Id of characteristic :i ro and r G A'ml a nonzero
rational function. Thin then t .rist jiolynomials a .b.c G A [n] such that h.c an
30


manic and
a(n)c(rt + 1)
r[n) = - -----------.
b(n) c( n)
inhere
1. ged(a(n).b{n h)) 1 far < cert) vonmyaliei ivl(

2. gcd(tHii).c(u)) = 1.
i. god(/)(n). c( n 1)) = 1.
Such polynomials are. eons! melt /I by Step 2 of Cospim's alyorilhm.
1. Prove this by letting i = j = .V in Proposition 4.2.
2. Assume that a{n) and c[n) have a noneonstant conunon factor. I lien so
do i>v[it] and Sj(n j). and from there, so do p\(n) and y,-\(n 2-h, j).
which contradicts Proposition 1.2.
3. Similarly to 2. assuming that b[n) and c(n -1) have' a noneonstant common
factor will lead to a contradiction of Proposition 1.2.
Lemma 4.4 L< I A be a Jit Id of eharaeh iislie y m. Let a.b.c. .4. B.C'.E. A n
b( polynomials such Hint gedf(n). c(n)) = gcdtA//). ofn 1)) = gcd(.4(n). B(n +
//)) = 1. for all nonniyuliv< inleyers h. If
a(n) c{n 1) A(n) C(n 1)
b[n) r(;?) B(n) Cin)
then c{n) il/ridts C{n).
Corollary 4.5 Lt I r(n) lx a ralionul fimelion. Thin lh< fncloriyilian r(n) =
n\ n i c' // l) ri'i / i
tr. /// I neon in 4.-1 is minim.
h 111 \ r( n) * 1


Corollary 4.6 Among all Iriphs a(n). b(n). c(n) salisfging /(//) =
and (4.4). Iln oik const racial in Slc/> 2 of Cospt r's algorithm has c{n) of hast
Gosper's algorithm dot's definitively answer the question lor which il was
developed. Il tells us whether a particular hypergeomotric term can be indefi-
nitely summed. This problem is somewhat analogous to the problem of solving
an indefinite integral. This leads us to wonder about what happens whim we
want the definite sum of a hypergoometric term (which would be analogous to
solving a definin' integral). Gosper's sum doesn't help us here. but. our next
algorithm will.


5. Zcilbcrger's Algorithm
Zcilbcrger's algoritlnn will help us find the definite sum of a hypergeometrie
term. It list's Gosper's algorithm and also expands upon the ideas of Sister
Mary Celine Fasenmyer's method. Again, this algorithm completely answers
the question of finding a definite sum of a hypergeoinetric term.
5.1 The Algorithm
Consider t lie sum
f{n) = ^2 k'(n.k).
/.
Like Sister Celine's method. we must first have a doubly hypergeometrie term,
i.e.. the ratio ' nnd the ratio ' art' both hvpergeometrie. Zeil-
hergers algorithm is also referred to as tin' Creative Telescoping method as we
shall later set'. Like Sister Celine's method. Zeilberger hist finds a. recurrence for
tilt' summand F(n.k) and then stuns over k to find the appropriate recurrence
for the sum fin). While we can't expect to always find a nice simple recurrence
like these
F{n. k) G{n. k + 1) Gin. k)
F(n + 1. k) F(n. k) G{n. k 1) Gin. k).
wc' are guarantt'ed by Theorem 3.2 to find some recurrence. In terms of'shift
operators [\ : cj[n.k) > (/{n.k 1) and A : f(n.k) fin \.k). and a
difference operator p : (n. X) > (loin) \ rq(/?)A r/-_ ( n) A2 . +

recurrence we are guaranired u> find is
p(n. X)F(n. k) = (I\ 1 )G(n. k).
The coefficients a,(>>) ar<' polynomials in u. and is a rational function of
n and k. so wo have'
.1
^ al{n)F{n -F j. k) = G(n. k 1) G{n. k). (5.1)
7=0
Once wo find. through Xeilbergor's algorithm. I he desired recurrence, we try
to sum over k to get our desired answer. 11 by chance our recurrence is a simple
linear recurrence, wo are happy as that is easy to solve. If the recurrence is not
linear but has constant coefficients, we are also comfortable. If neither of these
situations hold, wo still do not worry as that is where IVtkovsok's algorithm
"Hyper" conns into play. This algorithm will finish what Zeilberger started and
give us a complete answer to our question.
Begin with tin' recurrence (5.1) of order ./. Fix ./ and look for a recurrence.
(If we find no recurrence of order ./ then we next look for a recurrence of order
./+ 1.) For our fixed ./. tin' left side of (5.1) can be expressed as
tj. itoF(n.k) d[F(n + 1. Ad ... + a,/F(n J. AT (5.2)
Tin'll the consecutive term ratio is creatively written as
T-i _ + j-k \ 1 )/F(n. k + 1) F{n. k 1)
0 J2j=n r,7^r(" T j. k)/F( n. k) F(n.k)
The second fraction on the right is a rational function of /? and k. so write it as
h (n. k + 1 ) /'i (ii. k)
F(it.k) r>(n.k)
')
O
I


whore the rs an' polynomials. Since /(. k) was doubly hyporgeomot rie wo also
have that
F(n.k) agfn.k)
F{n l.k) so (/?./,-)
wluro the .s's are polynomials. Then
F(n + j. A') t-t F( n + j i. k) TT -sl(/i ~ J ~~ k k)
Fin.k) fjj Fin + j i l.k) ~~ 'WT ^ j > k)
With souk' substitution and simplification. w<' manipulate the consecutive term
ratio into the form
h\ Pu{k + 1) i'(k)
~77 ~ pF.k) s(/r)'
where th(' following equations hold.
./ j-i J
pFk) = ^ , .7 / A-) s-j(n + j i.k).
_/=() /=U /=/
,/
r(A-) = r, (/?. A-) J^[ s2(n + j /. A).
/=()
J
-s-(A-) = /_.(// A-) JJ So(n j !. k + 1).
/=(!
We know wo can write kll jn the canonical form ol Theorem 4.3
-Si /' !
so that
(3.1)
r[k) p\ik [ 1) p,(k)
s(A') Pi (Ay) /n,(A-)'
Now takep(A') = Pn(A-)pi(A') and from (5.1) and (5.5) we gi't:
/;.+1 p( A' + 1) p-2 i k)
Ac P(A') pF.k)
which is now in a form ready lor Step 3 ol (lospers algorithm.


Performing step '> of Gosper's algorithm, we find an u]J|kt bound. A. on llio
degree of our unknown equation l(k) such that
p-2{k)((k- 1) V)t'(k) =/>(/-)
What will result is a system of linear equations in .7 +-A + 2 variables: A + l from
f(k) and ./+ 1 from the coefficients fij(n). If a solution to this system dot's not
exist, then no telescoped veeuvrenee of order ./ exists, so we seek a recurrence of
order .J + 1. If however, we art' able to solve this system of equations then we
have' found all the Oj{n) coefficients from (5.1). Then we can find C!(n.k) from
the following:
CUn.k) -----((k)f/,.
lAk)
Tlif'ii wt' will sum both sides of (5.1) ovt'r k to get
Hopefully, from this point we can easily rewrite flit' recurrence to find our sum.
5.2 An example of Zcilbcrgcrs Algorithm
To compare this algorithm with Sister Celine's, wt' now perform Zeilberger's
algorithm on the same simple sum. Let
./
(5.G)
Then fix -7=1 and the consecutive term ratio is


We can expand and simplify this ratio to
b+i (/()(/( k) + r/1 (/ ? + 1) n k + I
f f: r/n( /? k +- 1) u i (n +- 1) k + 1
In terms of the general direct ions, we now have /;(/) = ait{n k + l) + <7|(n +- 1).
rlk) n k ~ 1. and s(k) = k 1. When we rewrite ~2 in the canonical form
of Theorem 4.3 we simply get that p\{k) = 1. /+>(/,) = n k 1. p-.fk) k 1.
and thus p{k) = Po{k)p\ [k) = po{k). The equation wi' must use to solve for L(k)
is
p-2{k)((k 1) p-.>Jk 1 )((k) = p(k).
(n k \)('{k +- 1) k( (k) ao(n k -f- 1) +- a i (n + 1).
Step 3 of Gosper's algorithm gives us an upper bound of 0 for the degree of ((k).
Thus ((k) = constant. Let 1 lie that constant. Then
tin k + 1) 3k = 0{)(n k 1) + a i (n T 1).
k{23) i- (3(n 1)) = k{au) (at}\n 1) 4- (iiiit D).
This gives the following system of equations.
-2 3 = -at) (3.7)
3(n + 11 = o(/< + l) i(/i 1) (3.8)
23 = and 3 (t0 +-i implies 3 (i\. So. in terms of 3 we have nn = 23.
cq 3. and 3 3. Now our n'currenci' in the form of 3.(3 is
2 3J(n) 3f( it 1) = (I.
Hence. f{n + 1 ) = 2 /(n). and using tin1 ini I ial value of /(()) 1. we obt ain
fin) = 2".
./> i


5.3 Analysis of Zeilberger's algorithm
Zeilberger's algoril Inn. lik<' Gosper's algorit Inn. completely answers I ho ques-
t ion at hand. Wo arc guaranlood a rcx-i naa n it a* of t lit' form (5.1) by Theorem 5.1
which wo will soon examine. Once we have the' roruiToneo relation, wo can ei-
ther find the closed form by hand or if the recurrence is complex we will use
lVtkovsek's algorithm "Hyper.'' The algorithm "Hyper will either return the
solution of the recurrence. f{n) (which could bo a linear combination of a fixed
number of hvpergeometrie terms), or will state that no such solution exists.
Theorem 5.1 Lit F'(n.k) lx a propi r hijpt rtp.onx trie term. Him F satisfies a
nontrivial reciinr ncc of the form (o.l). in which is a rational function of
n and k.
This theorem is proved using operator form. We have the shift operators _Y
and l\ as above, and so we write (3.7). the two term recurrence from Theorem
3.2. as
P(X. n. K)F(n. k) =-- 0.
In other terminology. P is an operator that annihilates F(n.k). We assume that
P is the annihilator of F(n.k) with the1 least degree in K. P is manipulated
using power series expansion so that we Inna'
0 = P(X. n. I\)F{n. k) (P{X. n. 1) (1 K)(}[X. n. [\))F(n. k).
where Q is a polynomial. Tin'll
P{X.n. n= (K 1)Q(.Y. n. K)F(n.k).
3S


Till' cm,so where P{>\. /f.l) 0 and llio caso where Q{.\.n.l\) = (J an* both
examined and found to possess nonzero A1-free operat ors which annihilate F(n. k)
wit h degree loss than P. This i> a eont radiot i< in of our original assumpt ions about
P.
)
O
{)


6. WZ Algorithm
T1k> WZ algorithm provides a proof cert ifieate as a way to verily the truth
ol a combinatorial identity. Differing from the previous two algorithms, the
main purpose of WZ is verification of an identity rather than solving a sum to
create an identity. As we will see. the WZ algorithm also makes use of Gosper's
algorithm. And after the basic verification, there are a few additional identities
that you get for free. What is impressive is that the proof certificate consists of
a single rational function. R[n.k). dims we have a great, way to find a concise
proof of a known identity. This method was developed by Herbert. Wilf and
Doron Zeilberger. thus the name "WZ."
6.1 The Algorithm
What we want to prove is t hat
If r(n) -f- 0. then divide both sides through by rln). Xow think of tlit' left hand
side as the new summand and we have
So now what we want to prove is that f(n) = F( n. k) is constant which we
will do by showing J'(n + 1) fin) = 0 lor all n. If wo can find a term G{n.k)
such t hat
y f(ri.k) = r{n)
F(n + 1. Ad Fi n. k) = Gln.k 1) Gl n. k).
(6.1)
It)


I hen when we Mini hot li sides of lIk- equal ion ovor k. \vp get f(n + 1 ) J(n) = 0.
A pair of functions. F and C. which satisfy (0.1) is called a \VX Pair. The third
function of relevance for this discussion is R(n.k) = tt"'1',. the proof certificate.
First wi' mention how to verify an identity from its proof certificate and
second we will consider how to form the certificate. R{n.k).
To prove an identity /(??. k) = r[n) front its proof certificate R(n. k). do
rho following.
1. If r(n) 7^ 0. then put F(n.k) cist' put F(n.k) = f(n.k). Li't
G{n.k) ~ H(n. k)F(n. k).
2. Verily that ((i. 1) is true. Write everything out. simplify, and verify the
polynomial ideal ity.
d. Verify that the' givt'ii identity is true1 for one value of /t[7 .
These steps are straight forward and only require algebra. As t he expressions
can be quite complex it is advisable to use a math soft wan' program.
To find a proof certificate for an identity do the following.
1. If r(n) ^ (). till'll put F(n.k) = yyyy-. else put F(n.k) = f(n.k).
2. Let f[k) F(n + 1. k) F(n.k). Input f(k) into Gosper's algorithm. If
Gospers algorithm fails, then the WX algorithm will too.
d. If suece.Mdul. the output (l(n.k) of Gosper's algorithm is the WX mate
of F. The rational function R(n.k) = is the WZ certificate of the
identity F(n.k) = constant^}.


6.2 An Example of the WZ Algorithm
Example 11. Suppose.' you are given the identity
and the proof cert ifieate
/?(//. k)
A'2 (3// 2k -f 3)
2(2n + 1)(// -k- 1)-
Tlien in order to verily this identity follow the appropriate stops above. First
write F(n.k) = and G(n.k) = R{>t. k)F(n. k) and simplily.
G{n. k)
F{n.k)
R{ it. k)F(n. k)
(2:) (2//)!A!2(// A')!'2'
k2(on 2k -r 3) W
"2(2/? b 1)(// k+ l)2) y (2//.)!A'!2(/? A-)!2
A;2(3/i -2A--3)//!1
2(2// + 1)!(// k 1)!2A-!2
Mow substitute' into (6.1). simplify, and verity the polynomial identifv.
(// + 1)!4 a!4
(2// + 2)!/d2(n 1 A-)!- ~~ (2n)!/d2(n /,-)!-
(3// 2/,- 1)/?!1 k2('.Ui 2/M-3)//!1
= 2(2// + l)!(a k)\-kl2 + 2(2// + 1 )!/,!-(// k l)!2'
Xow multiply both side's by '"~A i-2""2h. to gel
(// -i- 1) (/ / A' + 1 )_|2// + 2)|2// 1)
= (3// 2k + 1)(// 4- 1)(// k -p 1 )2 + IrC-kn 2k 3)(/? + 1).
Divide both side's by (n + 1).
(// + 1 f 2(// A- + 1)2(2// + 1) = (3// 2k + 1)(//. A- + 1 )2 A-2(3// 2k 3).
12


Using D('riv<* 6.
k2(ln 2) -f k{Sn2 12/? +1) 'In 7ir on 1
/.( 1/? 2) k[Sn2 + 12/? 1) j//' Tir on 1.
so tli(' polynomial identity holds. Xow we niusr check the identity tV>r one valtn
of /?. Let ?? = 3. Then we have
so we art' finished and have completely verified the given identity.
6.3 Analysis of the WZ Algorithm
One issue with the \YZ algorithm is that it depends upon Gosper's algo-
rithm. As we saw in (he steps to finding R(n.k). it Gosper's algorithm tails.
then so will this oik1. Now. we always have a recurrence of the form
./
^ aj{n)F[n j. k) G(n. k + 1) (Rn.k).
./=!)
and it has been observed [7] that UD/i of the tilin' tin' left hand side will reduce
to two terms to give ns the \\ Z equation!6.1).
The steps lbr verifying an identity and also for finding a proof certificate art'
bast'd on tin' following theorem. But first, we list some items relereuced in the
l lieorem.
1. For each integer k. the limit
/;, = lint F(//. k)
n x
exist s and is finite.
>
O


2. For each ini n > 0. wo have
lim Gin. k) 0.
k t X
2. Wo have ^(j>0 Gin. I,) = 0.
Theorem 6.1 Lt t {F.G) satisfy (d.l). If 2 abort bolds, then
yj F(n. k) ~ constant (n = 0.1.2....).
(6.2)
A-
If / and > abort both hold. Iht n trt hart tin com pan ion idt nlili/
J^G(n.k) = y (/, /'((-j))-
(621)
irhcrt f i.s dt final in 1 abort-..
This companion identity is one of tin' Tree" identities we yet when usiny
tlit' WZ alyoritlmi. This identity comes about because of the symmetry n and
k have in (6.1).
Proof: \\ o use the symbol A for the forward dillerence operator on n:
A/d'0 = bin + 1) bin) Sum hot h sides of t he WZ equat ion from k = L to
k = K. yett iny
Now let K.L > oo and use' 2 from abov(' to find that Fin. k) 0. i.o..
that Ylk /'(n-k) is independent of n > 0. which establishos (6.2). If we sum
both sides of ill*' WZ equation from n 0 to A we yet
A {AkGfn. k)} = Gin.F 1) Gin. L).
I I


Now l('l A" > ex) and use 1 above to cd
Jk ~ A (*). k) A*. < G(n. k) i .
. a.>u
Replace A by A:', sum from A-' = L to k' k 1. ltd L > oc. and us(' 3 abovt'
to obtain (G.3). This proof is taken from 7|.
As an illustration of the companion identity, consider our previous identity
E
Recall that Fln.k) = . and note that (using 1 above) f), = 0 for all values
of k. (J(n. k) can lie written as
-2A-- 3)
(!{n. k )
ui

2(2n 1) (A- 1)!-(// A-+ 1'
The companion identity we seek is ol the lorm
J^Ckn.k) = {/,-riu.j)).
>[)
So we have
E
/Ol)
-3/7 T 2A- 3)
,12
2(277- 1 ) (A- l)!-(n -A-+ 1)^(2//)
v- [ 0 >f A = 0
V (0- FiO.j)) = {
j 1
(3/7 2k 11 yf.j ^
^ (2/7 1}
which simplifies to
So tin' above identity is new and we gel it Iree when we use the \\ / algorithm.
Allot her identity that we will not explore here, is the dual identity ol a given


identity. Basically, you perform souk* operat ions on F and G. both lunations
of a \YZ ]>air. to obtain F' and G'. The exciting result is that F and G* arc
also a W Z pair, thus introducing another identity. In 7]. several other methods,
tlicks and ideas for delennining more' identities are discussed. This would be
interesting mat ('rial on its own for another paper.
In summary, the \YZ algorithm helps you to both verify an identity quite
easily and determine new identities from your original.
I(i


7. Algorithm "Hyper
This algorithm is used alter Zeilberger's algorithm when the recurrence re-
turned falls into one of the more' complex categories.
Through a strictly computational approach, algorithm Hyper finds a hy-
pergeometric solution of Li/ f where L is a linear recurrence operator. For
additional clarification, consider that
r
L = ^ p, (a) X'
(=0
where N is the shift operator mentioned in the explanation of Zeilberger's algo-
rithm.
Since' the algorithm Hyper makes use of a subroutine', algorithm Poly, we.'
cemsideT the' subroutine* first.
7.1 "Poly
The input is the' set of polynomials. p,{n ) ove'r F. a fie'lel. for i = 0. 1..r.
where r is the' degree of The output is the* ge'ne'ral polynomial solutiem of
I.y = f. do perform this algorithm, use the following steps.
1. Compute* q, = £f=j (')/L for () < J < >'
2. Let de'gO = og and let b max {deg e/. j}.
" r <
3. Let a(.r) = lc (e/7) .C where* lc (qj) denote's the hauling oex'ffi-
() tk'jj; Hjj ^
cient of (ha polynomial qr aiul J- is l ho falling factorial j;(s 1) . (y
i


]. Let d] = max{.r 6 Z+ U {()} : o(.t') = I)}.
o. Compute d using d = max {deg / b. h 1. r/t} .
(j. Using tin' method of undetermined coefficients, find all i/(n) of the form
//(") = that satisfy Iaj = /.
Example 12. Find the polynomial solutions of
Uj(n + 2) ny[n + 1) + (/?. 1);/() = 0.
Use the steps above1 to identify the following.
Puin) = ii l. Pi{n) = n. and pu(n) = 3.
U> = E=o (o)lJt = (n)/A) + (u)pi ~ (u) Pi = Pc ~ Pi + Pi n 1 n + 3 = 2.
C = E?=i G)/f = (J)Pi + (f)^j = yJi -f- 2p> = -n + 2(3,) = (>
di = EL, G)c = C])tt2 = Pi =
deg 0 oo. and b = max{() 0. 1 1. 0 2} = 0.
o(.r) = 2.r- .i- = 2 x. and di = max{2} = 2.
d = max{ oo 0. 0 1. 2} = 2.
So now we1 can use the method of undetermined coefficients to find
ij(ii) = cun0 op/1 c->ir
sat islying
3(C|i + C\ (n 2)1 C2[ n + 2)~) n{ Cu + C\ (n 1)1
+C'2(n + 1)) + (ii 1) (Cu + C\ n1 ran ) = 0.
18


Kquating tin1 coefficients of powers of u to zero yields the following syst('in of
equal ions:
2c|| -)- d(] + 12C-> ()
(7.1)
0) + 1 bo = 0.
(7.2)
Let tiny c-2 1 gives
y(n) = 2711 n ir.
7.2 "Hyper'"
As previously mentioned. Hyper makes use of Poly as a son of subroutine.
Again, there is much notation that must be organized and prepared in order to
clearly navigate the algorithm.
The input is again the set of polynomials. p,ln) over F. a Hold, for i =
0.1.....d when' d is the degree of Iaj. Also, input K. an extension Held of F.
The output this time will be a hypergeometric solution of Ly = 0 over I\ if one
exists and 0 otherwise. The execution of this algorithm consists of the following
steps.
1. For all monic factors a(n) of pu[n) and b{n) of p,i(n d 1) over I\ do:
Let P,[n) = p,{n) (// +j) n,=i ^ +2)- Ior = ()- ]....(,:
Li'l m = niax0<,<,/deg P;(n):
Lct n, be the coefficient of n"1 in P-,{n). for / = ().!........d:
for all nonzero E A such that
;=o
19


do:
H the l'f'cum'iicc
,i
Y ~Pi{n)c()> i) = 0
/ = ()
lias a nonzero polynomial solution c(n) over l\ them
lot Sin) = :{a{n)/b{n))(c(n 1)/V(/?));
return a nonzero solut ion i/( n) of//(//-rl) = S(n)t/[n) and
stop.
2. Return 0 and stop.
7.3 Examples Using Algorithms Poly and Hyper
\Ye now attempt an in-depth example using both algorithms.
Example 13.
Find the hypergeonietrie solution of
(n 1 )p[n -f 2) (ir on 2)y(n + 1) 2n(n + 1 )y(n) 0.
First identify the p,in)'>. pui.n) -- 2n(n 1). pi{n) = (n2 -in 2)
p>(n) = it 1. Notice* that a{u) could equal 1. n. n + 1. n{n 1).
b(n) could c(jual 1. n 2.
This would require that we perform tin' main loop in Hyper 8 time's once
for each combination of a(n) and b(n).
We will perform 2 case's completely and then mention what happens in the
other G case's.
AO


Case 1
Lot. a(n) = 1 and b(n) = 1. Thru Pa{n) = 2/?( n A 1). Pj (/?) = {n2 3/? 2).
and Pop?.) = /? 1. Also, /?? = 2. on = 2. 0| = 1. and no = 0. Thus equation
(7.3) is 2 : = 0 so = 2.
The recurrence for which wo now dosin' to find polynomial solutions is
2/?(// + 1 )r(n) 2(/?2 -f 3/? 2)r( n 1) 4- 4( n 1 )r( /? + 2) = 0. which reduces to
??( ?? A 1 )c(n) (tr 4- 3/7 2)r(/? 1) A 2(/? 1 )r( /?) = 0.
This is the rf'ciirrcnct' we will food into the algorithm Poly.
Pi,i n) = ??2 ??. />[(/?) = (n2 3/? 2). and pP n) = 2)7 2.
rjD = pa + pi A /to = 0. q, = pj 2/to = n 2. and r/o = /m = 2/? 2.
deg 0 = og. and b = max{(! 0. 21. 1 2} = 1.
o(.?) = a = x. and di = max{()} = 0.
d = max{ oo 1. 1 1. I)} = 0.
So now we can use' the method of undetermined coefficients to find
t/( n) = Call0
satisfying
//(/? A l)c (tr A 3/? 2)c 2(n l)e = 0.
This statement is valid lor all c(i. so lot. e = 1. Poly returns t he solntion c(n) = 1.
Now w(> go hack to Hyper to continue. We find that
c, 1 bin) c(n) 1 1
Then we have ?/(?? A I) = 2/y{//) and so onr final solution to case 1 is //(??) = 2". ol
ol


Cast' 2
Let. o() = /? and b(n) ~ 1. I'Ikmi Pain) = 2n(nP\). Pt (n) = n[n2T3// 2).
and P-zin) = (n 1)(/?)(/? 1). Also, in = 3. nn 0. rq 1. and rto = 1. Tims
aquation (7.3) gives : + :J = 0 so ; = 1.
The recurrence lor which we now desire to find polynomial solutions is
2n{n + 1 )e(n) n(n2 T 3 2)r(n 4- 1) + (/? 1)/?(/? -f 1 )r(n 2) = 0.
This is the recurrence we will fet'd into the algorithm Toly.
Pn( ft-) = 2n2 2n. pi{n) ~ (;?,! 3n2 2n). and />>(??) = n2 n.
Qw = Pa + Pi p-2 = 2 + 3/?. q\ = p) -t- 2p2 = ir 3/?-. and cp = p? = n2 .
degO = oc. anrl b max{2 I). 3 1. 3 2} = 2.
n(.r) = -.r- + .r- = 1 + .r. and <7i = max{l} = 1.
<7 = max{oo 2. 21. 1} = 1.
So now we can list' tilt' liK'thod of undetermined coefficients to find
p{n) = c(l/in ci/i1
sat isfying
2/?I //T1)(c(i+C| /?1) /?.(/?.+3/? 2)(Co+C| (//1 1 )1) T( n 1 )n(n + 1)(cyC\ (nT2) ) = 0.
This statement is valid for all eg when cn 0. so let rA = 1. Poly returns
tlit' solution c(n) = n. Now we go back to Hyper to continue. Wo find that
a{n) c[n T 1) n n 1 n[n f 1)
At n) =
1 -
= n 1.
b[n) c(n) 1 n
Th('n wt' have t/(n + 1) = (n !)//(/<) and so our final solution to case 2 is
yin) = nl.
Now wt' examine what happens in the rest of the cast's.
52


a( ii) 1) (11)
result
1 n-2 Equation (7.A) lias no solution
n n-2 z=2. hut o(.r ) = 2 ./ which has no nonnegativc solutions.
mol 1 the' algorithm works and we get a previous answer y(n)=u!.
11-I n-2 z=2. but o(.r ) = d .r which has no nonnegativc solutions.
11(11 1) 1 E(]uation (7..+) has no solution
n(n+l) n-2 z1. but 0 (.. r) = 2 .r which has no nomn'gative solutions.
After inspc'c-till' each of the eight cases, we see that the two viable' solutions
an1 y(n) = n\ and y(n) = 2". Thus, the' hypei-geometric solution to our original
recurrence' is 1/(71) = C2" + Dn\. wlie're ('. D are' arbitrary constants.


8. Summary
In summary. Gosper's algorithm and Ze'ilbe'rger's algorithm together with
algorithm "Hypen" complete'ly answe-r tlu' questions of summing indefinite
and definite' hypergeometric sums respe'cfively. The' solutions are fully algorith-
mic and will ('ither return the* desired results or return a message saying tIkto
is no solution. The inputs must be' proper hype'rge'ome't.ric sums and the1 closexl
form output will be a line'ar combination of liypeTge'omel rio teams. We do not
have.' a guar;mt('(' that a certain sum will be1 able to be' writte'ii in hypergeometrie
closed form, but we do have' a theore'in guaranteving we can find a re'eurrence'
relation for each sum. The problem sometime's comes when we try to find a
solution for the recurre'ttce'.
The* \VZ algorithm significantly cuts down on the' length of proofs and gives
a proof certificate for which it is easy to venify the proof. It also providers a means
to find additional identit it's both as a byproduct of the standard operation
and as a separate topic on its own.
All in all. event with the lew shortcomings they have', these cotnpul e'rixe'd
algorithms have fremenidously aided mat homaticicans in tlie'ir (|uest to find com-
binatorial ide'iit it it's.


REFERENCES
jll BOROS. G. and Moll. Y.H. The. double square root. Jacobi polynomi-
als and Banmnujern's Master 'Theorem. in .Journal of Computational and
Applied Mathematics. Yol 130. Issues 1-2. May 2001. pp. 337-344.
[2] Chapman. Robin J. .4 Sniu-tmfrh mlly Identity A solution to AMM
problem 10200. in American Mat hemal ical .Monthly Yol. 102. Xo. 7. Aug-
Sep. 1995. pp. 057-058.
[3 GOSPER. R.W ...Jr. Decision procedure [or indefinite hype ryeomc.lric sum-
mation. Proc. Xatl. Acad. Sci. USA 1975.
[ 1] Hsu. Fang.JUN: AND Hsu. Leetsch. C. .4 uni/icel trail went of a class of
combinatorial sums Discrete Mathematics. Yol 90. 1991. pp. 191-197
[5' Lin. Shy-Der: Sriyastaya, H.M.: and Wang. Pin-Yu Some mi.red
mull iJat i ra I ye ne ratiny relations inrolriny hype rye trine trie functions. Inte-
gral Transforms and Special Functions. Yol 10. Xo. 8. Dec. 2005. pp. 009-
014
[(i; ODLYZKO. A.M. Asymptotic e ntime ration imthoels. in Handbook of ('om-
binatorics. yol. 2. R. L. Graham. M. Groetschel. and I.. Lovasz. eds.. Else-
vi(T. 1995. pp. 1003-1229.
[71 Petkoysek. Marko; Wile. Herbert S.; and Zeilberger, Doron
A=B. A K Peters. Wellesley. MA. 1990.
[s] R.oy. R.A.n.JAN Binomial Ide ntities and Ilyperyeomctrie Scrie s in American
Mathematical Monthly Yol. 94. Xo. I. Jan. 1987. pp. 30-40
[9 Sylvester. J..J. A Method of Dctc.nnininej By Mere Inspection the. Drrirei-
tives from liro liquations of Any Dee/re e Phil. Mag. 10. 1840. pp. 132-135.
10 VAN HaERINGEN. H. An Application of Snake Oil A solution to AMM
problem 10388. in American Mathematical Monthly Yol. 104. Xo. 5. Maw
1997. i)i>. 459-100.
11 WlLF. HERBERT S. yeneralinyfunclionoloyy. Academic Press Inc.. San
Diego. CA. 1990.
oo


12' Wilf. Herbert S. and Zeieberger. Dorox An AUjorithwic proof Hu.
ortj for hijp( lytumiclric (ordinary and "q") m till iruin/in Itpnd /dullili( s. In
voiitionas Mat hemal ica\ Vol 108. 1002. pp. 575-033.
1131 ht t p://mat h world, wolfram. ('om/Ch'iKrat inghnnct ion.lit ml 4/3/2000
14: http://mathworld.wolfram.< om/IIvpiTgoometrk Serins.html 4/3/2000
,15 http://mat liworld. wolfram.com/Canonicalkorm.lit ml 1/4/2006
do lit.t.p://oii.wikip('>(lia.or<>7wiki/Ca.mmioal_ form/ 4/4/2000
17i http://phmetmath.org/encvelopodia/Resultant.html 3/31/2000
18] http://om wikipodia.org/wiki/Ant omated_thooroin_proving 4/10/2000
50