Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00004216/00001
## Material Information- Title:
- The mechanization of the proofs of combinatorial identities
- Creator:
- Venter, Alexsis M
- Publication Date:
- 2006
- 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 )
## Auraria Membership |

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 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 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 - 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 \ 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 (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 (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). 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 (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 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 < il 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 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. |