{VERSION 2 3 "SUN SPARC SOLARIS" "2.3" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 256 "terminal" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE " " -1 257 "" 1 24 0 0 0 0 0 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Co urier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 "" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }{PSTYLE "Warning" 2 7 1 {CSTYLE "" -1 -1 "" 0 1 0 0 255 1 0 0 0 0 0 0 1 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Error" 7 8 1 {CSTYLE "" -1 -1 "" 0 1 255 0 255 1 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Map le Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 " " 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 } {PSTYLE "" 3 256 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } 3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 0" -1 257 1 {CSTYLE "" -1 -1 "Helvetica" 1 14 0 0 0 0 2 1 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "R3 Font 2" -1 258 1 {CSTYLE "" -1 -1 "Courier " 1 14 0 0 0 0 2 2 2 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 41 "/home/m262f99/KOEPF/works heetsV.4/hw4.mws" }{MPLTEXT 1 0 0 "" }}{PARA 256 "" 0 "" {TEXT 257 45 "Math 262a, Fall 1999, Glenn Tesler\nHomework 4" }{MPLTEXT 1 0 0 "" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "read `hsum.mpl`;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%ZCopyright~1998~~Wolfram~Koepf,~Konrad-Zuse -Zentrum~BerlinG" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 9 "Problem 1" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 91 "First of all, the computer can gen erate the recurrence that is given to you in the problem:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 105 "rec_cer := sumrecursion(2^k * n/(n-k) * bin omial(n-k,2*k), k=0..n/3, f(n), certificate=true);" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#>%(rec_cerG7$/,*-%\"fG6#,&%\"nG\"\"\" \"\"$F-!\"\"-F)6#,&F,F-\"\"#F-F3-F)6#,&F,F-F-F-F/-F)6#F,F3\"\"!,$*.,&F ,F/%\"kGF-F-,&F=F3F/F-F-F=F-,(F,F/F=F.F/F-F/,(F=F.!\"#F-F,F/F/,(F,F/F= F.!\"$F-F/F3" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 222 "To recover what' s on the problem, replace s(n+i) by F(n+i,k) in the recurrence (first \+ return value); and the second return value is R(n,k). Multiply it by \+ F(n,k) to get G(n,k), then make the right side be G(n,k+1)-G(n,k)." }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "factor(-E^3+2*E^2-E+2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,$*&,&%\"EG\"\"\"!\"#F'F',&*$F&\"\"#F' F'F'F'!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "so evidentally the left side of the recursion has an overall minus sign from what's give n" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "F1 \+ := 2^k * n/(n-k) * binomial(n-k,2*k);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G**)\"\"#%\"kG\"\"\"%\"nGF),&F*F)F(!\"\"F,-%)binomialG6$F+,$F( F'F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "R1 := rec_cer[2];\n G1 := F1*R1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#R1G,$*.,&%\"nG!\"\" %\"kG\"\"\"F+,&F*\"\"#F)F+F+F*F+,(F(F)F*\"\"$F)F+F),(F*F/!\"#F+F(F)F), (F(F)F*F/!\"$F+F)F-" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#G1G,$*6)\"\" #%\"kG\"\"\"%\"nGF*,&F+F*F)!\"\"F--%)binomialG6$F,,$F)F(F*,&F+F-F)F*F* ,&F)F(F-F*F*F)F*,(F+F-F)\"\"$F-F*F-,(F)F5!\"#F*F+F-F-,(F+F-F)F5!\"$F*F -F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "simplify(-2^k*n/(n-3 *k+3) * binomial(n-k,2*k-2) / G1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# ,$*.,(%\"kG\"\"$!\"#\"\"\"%\"nG!\"\"F),(F*F+F&F'F+F)F)-%)binomialG6$,& F*F)F&F+,&F&\"\"#F(F)F)F&F+,&F&F2F+F)F+-F.6$F0,$F&F2F+#F+F2" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "simpcomb(\");" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "s o the right side has a negative also. So Koepf's program deduced some thing equivalent to what's stated. Now verify it." }}{PARA 3 "" 0 "" {TEXT -1 10 "Problem 1a" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "lh := su bs('f(n+i)=subs(n=n+i,F1)'$i=0..3, lhs(rec_cer[1]));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#lhG,***)\"\"#%\"kG\"\"\",&%\"nGF*\"\"$F*F*,(F,F*F -F*F)!\"\"F/-%)binomialG6$F.,$F)F(F*F/**F'F*,&F,F*F(F*F*,(F,F*F(F*F)F/ F/-F16$F6F3F*F(**F'F*,&F,F*F*F*F*,(F,F*F)F/F*F*F/-F16$F;F3F*F/**F'F*F, F*,&F,F*F)F/F/-F16$F?F3F*F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "rh := subs(k=k+1,G1)-G1;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#rhG ,&*6)\"\"#,&%\"kG\"\"\"F+F+F+%\"nGF+,(F,F+F*!\"\"F.F+F.-%)binomialG6$F -,&F*F(F(F+F+,(F,F.F*F+F+F+F+,&F*F(F+F+F+F)F+,(F,F.F*\"\"$F(F+F.,(F*F6 F+F+F,F.F.,&F,F.F*F6F.F(*6)F(F*F+F,F+,&F,F+F*F.F.-F06$F;,$F*F(F+,&F,F. F*F+F+,&F*F(F.F+F+F*F+,(F,F.F*F6F.F+F.,(F*F6!\"#F+F,F.F.,(F,F.F*F6!\"$ F+F.FC" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "simplify(lh/F1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$**,6*$%\"kG\"\"$\"#D*&%\"nG\"\" \"F'\"\"#!#D*$F'F-!#`*&F+F-F'F,\"\"**&F+F,F'F,\"#NF'\"#L*$F+F(!\"\"F+! #6!\"'F,*$F+F-F9F,,(F+F7F'F(F7F,F7,(F'F(!\"#F,F+F7F7,(F+F7F'F(!\"$F,F7 F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "simplify(rh/F1);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#,$**,6*$%\"kG\"\"$\"#D*&%\"nG\"\"\"F' \"\"#!#D*$F'F-!#`*&F+F-F'F,\"\"**&F+F,F'F,\"#NF'\"#L*$F+F(!\"\"F+!#6! \"'F,*$F+F-F9F,,(F+F7F'F(F7F,F7,(F'F(!\"#F,F+F7F7,(F+F7F'F(!\"$F,F7F- " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 5 "\"-\"\";" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 "The \+ verification is complete." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 " " {TEXT -1 10 "Problem 1b" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 119 "The bounds k=0..floor(n/3) aren't natural: the denomin ator n-k cancels off the n-k from (n-k)! in the numerator, giving" }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "F1b := simpcomb(F1);" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%$F1bG*,-%&GAMMAG6#,&%\"nG\"\"\"%\"kG!\"\"F+F*F +)\"\"#F,F+-F'6#,&F,F/F+F+F--F'6#,(F*F+F,!\"$F+F+F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "and the k-support at n is k=\{0,1,...,floor(n/3 ), n,n+1,n+2,...\}; for example," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 52 "'` F1`(10,kk)=limit(subs(n=10,F1b),k=kk)'$kk=-3..13;" }}{PARA 12 "" 1 "" {XPPMATH 20 "63/-%$~F1G6$\"#5!\"$\"\"!/-F%6$F'!\"#F)/-F%6$F'!\"\" F)/-F%6$F'F)\"\"\"/-F%6$F'F5\"#!)/-F%6$F'\"\"#\"$]$/-F%6$F'\"\"$F9/-F% 6$F'\"\"%F)/-F%6$F'\"\"&F)/-F%6$F'\"\"'F)/-F%6$F'\"\"(F)/-F%6$F'\"\")F )/-F%6$F'\"\"*F)/-F%6$F'F'!%O:/-F%6$F'\"#6!&S9'/-F%6$F'\"#7!(+g`\"/-F% 6$F'\"#8!)gd'4$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 340 "but we do hav e F(n,k)=0 for k=floor(n/3)+1,floor(n/3)+2,...,n-1. From now on we mu st assume n>=2 because otherwise this k-range just given is empty, and we're assuming it's not.\nThe recursion involves f(n),f(n+1),f(n+2),f (n+3), and in all these the parameter is different, so the summation r ange is slightly different.\nSo take the relation" }}{PARA 0 "> " 0 " " {MPLTEXT 1 0 54 "-(En^2+1)*(En-2)*` F1`(n,k) = ` G1`(n,k+1)-` G1`(n, k);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,$*(,&*$%#EnG\"\"#\"\"\"F*F*F* ,&F(F*!\"#F*F*-%$~F1G6$%\"nG%\"kGF*!\"\",&-%$~G1G6$F0,&F1F*F*F*F*-F5F/ F2" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 86 "and sum both sides from k=0 ..floor(n/3)+1. The terms on the left side still add up to" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "lhs(rec_cer[1]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,*-%\"fG6#,&%\"nG\"\"\"\"\"$F)!\"\"-F%6#,&F( F)\"\"#F)F/-F%6#,&F(F)F)F)F+-F%6#F(F/" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 80 "because we have added 0 to some of these. The terms on t he right side add up to" }}{PARA 0 "" 0 "" {TEXT -1 86 "G1(n,floor(k/3 ) + 2) - G1(n,0) = 0 - 0 = 0. This proves the recursion above equals \+ 0." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 82 "Now evaluate f(n). It's a \+ constant coefficient recurrence with roots i, -i, 2, so" }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 34 "fn := c1*I^n + c2*(-I)^n + c3*2^n;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#fnG,(*&%#c1G\"\"\")%\"IG%\"nGF(F(*&%#c2GF (),$F*!\"\"F+F(F(*&%#c3GF()\"\"#F+F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "ff := nn -> sum(subs(n=nn,F1),k=0..nn/3); # maple tru ncates to floor(n/3)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#ffG:6#%#nnG 6\"6$%)operatorG%&arrowGF(-%$sumG6$-%%subsG6$/%\"nG9$%#F1G/%\"kG;\"\"! ,$F4#\"\"\"\"\"$F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 26 "Plug in i nitial conditions" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "'subs(n=nn,fn) = ff(nn)'$nn=2..4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%/,(%#c1G!\"\"%# c2GF&%#c3G\"\"%\"\"\"/,(*&%\"IGF*F%F*F&*&F.F*F'F*F*F(\"\")F)/,(F%F*F'F *F(\"#;\"\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "solve(\{\" \}, \{c1,c2,c3\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%/%#c1G#\"\"\" \"\"#/%#c2GF&/%#c3GF&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "su bs(\",fn);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,()%\"IG%\"nG#\"\"\"\"\" #),$F%!\"\"F&F')F)F&F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "fn 2 := \":" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Now check it." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "for nn from 0 to 10 do\n prin t(`actual f`(nn)=ff(nn),\n `new formula for f`(nn)=simplify (subs(n=nn,fn2)));\nod;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~ fG6#\"\"!F'/-%2new~formula~for~fGF&#\"\"$\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"\"F'/-%2new~formula~for~fGF&F'" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"#\"\"\"/-%2new~form ula~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"$ \"\"%/-%2new~formula~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-% )actual~fG6#\"\"%\"\"*/-%2new~formula~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"&\"#;/-%2new~formula~for~fGF&F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"'\"#J/-%2new~formul a~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"(\" #k/-%2new~formula~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)ac tual~fG6#\"\")\"$H\"/-%2new~formula~for~fGF&F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"\"*\"$c#/-%2new~formula~for~fGF&F(" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$/-%)actual~fG6#\"#5\"$6&/-%2new~formul a~for~fGF&F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "We see that it ha ppens to hold for n=1 by accident, and indeed does not hold for n=0." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 3 "" 0 "" {TEXT -1 9 "Problem 2" }}{PARA 0 "" 0 "" {TEXT -1 19 "The examples shown:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "sumre cursion(binomial(n,k),k,s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&- %\"sG6#,&%\"nG\"\"\"F*F*!\"\"-F&6#F)\"\"#\"\"!" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 33 "zeilberger(binomial(n,k),k,s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&-%\"sG6#%\"nG\"\"#-F&6#,&F(\"\"\"F-F-!\"\"\" \"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "fasenmyer(binomial(n ,k),k,s(n),0);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error, (in kfreerec) no kfree recurrence equation of order (, 0, 0, ) exists" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "fasenmyer(binomial(n,k),k,s(n),1); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&-%\"sG6#,&%\"nG\"\"\"F*F*F*-F&6 #F)!\"#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "closedform( binomial(n,k),k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#)\"\"#%\"nG" }} }{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "Closedform(binomial(n,k),k, n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%*HypertermG6&7#\"\"\"7\"\"\"# %\"nG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 68 "and now doing the given \+ problem with each of the various algorithms:" }{MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "closedform(binomial(n,k)^3,k ,n);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error, (in zeilberger) algorithm \+ finds no recurrence equation of first order" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "rec1 := sumrecursion(binomial(n,k)^3,k,s(n));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%rec1G/,(*&,&%\"nG\"\"\"\"\"#F*F+-% \"sG6#F(F*!\"\"*&,(F)\"#@*$F)F+\"\"(\"#;F*F*-F-6#,&F)F*F*F*F*F**&F8F+- F-6#F)F*\"\")\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r1 := lhs(rec1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#r1G,(*&,&%\"nG\"\"\" \"\"#F)F*-%\"sG6#F'F)!\"\"*&,(F(\"#@*$F(F*\"\"(\"#;F)F)-F,6#,&F(F)F)F) F)F)*&F7F*-F,6#F(F)\"\")" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "Creat ive telescoping found a recurrence of order 2. Try that for Celine's \+ algorithm." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "fasenmyer(binomial(n, k)^3,k,s(n),2);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error, (in kfreerec) n o kfree recurrence equation of order (, 2, 2, ) exists" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "fasenmyer(binomial(n,k)^3,k,s(n),3) ;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,**(,&%\"nG\"\"$\"\"%\"\"\"F*,&F 'F*F(F*\"\"#-%\"sG6#F+F*F**&,**$F'F(\"\"**$F'F,\"#dF'\"$;\"\"#uF*F*-F. 6#,&F'F*F,F*F*!\"#*(,&F'F(\"\"&F*F*,(F4\"#:F'\"#b\"#[F*F*-F.6#,&F'F*F* F*F*!\"\"*(,&F'F(\"\"(F*F*FEF,-F.6#F'F*!\")\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "rec2 := \":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "r2 := lhs(rec2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#> %#r2G,**(,&%\"nG\"\"$\"\"%\"\"\"F+,&F(F+F)F+\"\"#-%\"sG6#F,F+F+*&,**$F (F)\"\"**$F(F-\"#dF(\"$;\"\"#uF+F+-F/6#,&F(F+F-F+F+!\"#*(,&F(F)\"\"&F+ F+,(F5\"#:F(\"#b\"#[F+F+-F/6#,&F(F+F+F+F+!\"\"*(,&F(F)\"\"(F+F+FFF--F/ 6#F(F+!\")" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 308 "They appear to be \+ different!\nBut remember, any recursion can be \"multiplied\" by a pol ynomial in n and E to give a higher order recursion. So we could have r2 = (A+B*E)*r1, where A,B are polynomials in n; or it could be the f unction really satifies an order 1 recurrence, and r1, r2 are both mul tiples of it." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 225 "Set up the equa tion r2 - (A+B*E)*r1 = 0.\nCollect it by s(n),s(n+1),...\nThe coeffi cients of s(n), s(n+1),... on both sides must agree, hence the coeffic ient on the left must equal 0. This gives a system of equations in A, B." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Er1 := subs(n=n+1,r1) ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$Er1G,(*&,&%\"nG\"\"\"\"\"$F)\" \"#-%\"sG6#F'F)!\"\"*&,(F(\"#@\"#PF)*$,&F(F)F)F)F+\"\"(F)-F-6#,&F(F)F+ F)F)F)*&F9F+-F-6#F5F)\"\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "ss := \{'s(n+i)'$i=0..3\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s sG<&-%\"sG6#%\"nG-F'6#,&F)\"\"\"F-F--F'6#,&F)F-\"\"#F--F'6#,&F)F-\"\"$ F-" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "collect(A*r1 + B*Er1 \+ - r2,ss,factor);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,**(,&%\"nG\"\"\"F 'F'\"\"#,(F&\"\"$%\"AGF'\"\"(F'F'-%\"sG6#F&F'\"\")*&,6*&%\"BGF'F&F(F0* &F4F'F&F'\"#KF4F6*&F+F'F&F'\"#@*&F+F'F&F(F,F+\"#;*$F&F*\"#X*$F&F(\"$S# F&\"$>%F>F'F'-F.6#F%F'F'*&,6F9!\"\"F7!\"%F+FEF;\"#=F=\"$9\"F&\"$K#\"$[ \"F'F5\"#NF4\"#WF3F,F'-F.6#,&F&F'F(F'F'F'*(,&F&F'F*F'F(,(F&F*F4F'\"\"% F'F'-F.6#FPF'FD" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "coeffs( \",ss);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6&,$*&,&%\"nG\"\"\"F'F'\"\"#, (F&\"\"$%\"AGF'\"\"(F'F'\"\"),6*&%\"BGF'F&F(F-*&F0F'F&F'\"#KF0F2*&F+F' F&F'\"#@*&F+F'F&F(F,F+\"#;*$F&F*\"#X*$F&F(\"$S#F&\"$>%F:F',6F5!\"\"F3! \"%F+F>F7\"#=F9\"$9\"F&\"$K#\"$[\"F'F1\"#NF0\"#WF/F,,$*&,&F&F'F*F'F(,( F&F*F0F'\"\"%F'F'F=" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "solv e(\{\"\},\{A,B\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$/%\"BG,&%\"nG! \"$!\"%\"\"\"/%\"AG,&F'F(!\"(F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "subs(\", A+B*E);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(%\"nG!\" $!\"(\"\"\"*&,&F$F%!\"%F'F'%\"EGF'F'" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 565 "Thus, the se cond recurrence is -[(3n+7)+(3n+4)E]*first recurrence.\nSC is Sister Celine's algorithm, CT is Zeilberger's Creative Telescoping.\nNote SC succeeds implies CT succeeds (and with a possibly smaller order recur rence), but not conversely.\nSC finds a homogeneous recurrence of unkn own orders in n,k for F(n,k), then converts it to a recurrence for f(n )=sum_k F(n,k).\nCT finds a nonhomogeneous recurrence for f(n) of unkn own order in n alone, so there may not even be a recurrence for F(n,k) , or it may exist, but with higher n-order than necessary for f(n)." } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 " " {TEXT -1 9 "Problem 3" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 9 "Koepf 7.4" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 3 "Let" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "Sum(a[i](n)*s(n+ i),i=0..K)=0;\nSum(b[i](n)*s(n+i),i=0..K)=0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%$SumG6$*&-&%\"aG6#%\"iG6#%\"nG\"\"\"-%\"sG6#,&F.F/F, F/F//F,;\"\"!%\"KGF6" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%$SumG6$*&-& %\"bG6#%\"iG6#%\"nG\"\"\"-%\"sG6#,&F.F/F,F/F//F,;\"\"!%\"KGF6" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 538 "be two recurrence equations satis fied by s(n) of the same minimal order K. The first equation minus a_ K(n)/b_K(n) * the second equation has order at most K-1, and thus is 0 =0 because K was minimal. Thus, any two equations of minimal order ar e rational multiples of each other. Clearing denominators and removin g all common factors, we can get the a_i(n)'s to be polynomials s.t. g cd(a_0(n),a_1(n),...,a_K(n))=1, and then all other recurrences of orde r K with polynomials in n as coefficients must be a polynomial multipl e of this one. " }{MPLTEXT 1 0 1 " " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 3 "" 0 "" {TEXT -1 9 "Koepf 7.7" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "sumrecursion(hyperterm([a,b],[c+m],1,k),k,s(m));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*(,(%\"bG\"\"\"%\"cG!\"\"%\"mGF*F(, (%\"aGF(F)F*F+F*F(-%\"sG6#,&F+F(F(F(F(F(*(,&F)F(F+F(F(,*F-F(F'F(F)F*F+ F*F(-F/6#F+F(F(\"\"!" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 10 "Koepf 7.1 0" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "sumrecursion(binomial(n,k)*poc hhammer(x,k)*pochhammer(y,n-k),k,s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&-%\"sG6#,&%\"nG\"\"\"F*F*!\"\"*&,(%\"yGF*%\"xGF*F)F*F*-F&6#F) F*F*\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 64 "closedform(bin omial(n,k)*pochhammer(x,k)*pochhammer(y,n-k),k,n);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#-%+pochhammerG6$,&%\"yG\"\"\"%\"xGF(%\"nG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 21 "Koepf 7.11\nKrawtchouk" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "su mrecursion((-1)^n*p^n*binomial(N,n)*hyperterm([-n,-x],[-N],1/p,k),k,K( n));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,(*&,&\"\"#\"\"\"%\"nGF(F(-% \"KG6#F&F(F(*&,.%\"pGF'!\"\"F(*&F/F(%\"NGF(F0F)F0*&F)F(F/F(F'%\"xGF(F( -F+6#,&F(F(F)F(F(F0**F/F(,&F0F(F/F(F(,&F2F0F)F(F(-F+6#F)F(F(\"\"!" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "sumrecursion((-1)^n*p^n*bino mial(N,n)*hyperterm([-n,-x],[-N],1/p,k),k,K(x));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,(*(%\"pG\"\"\",(%\"xGF'%\"NG!\"\"F'F'F'-%\"KG6#,&F)F' \"\"#F'F'F'*&,.F&F0F+F'*&F&F'F*F'F+F)F+*&F)F'F&F'F0%\"nGF'F'-F-6#,&F)F 'F'F'F'F+*(F8F',&F+F'F&F'F'-F-6#F)F'F'\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 76 "sumrecursion((-1)^n*p^n*binomial(N,n)*hyperterm([- n,-x],[-N],1/p,k),k,K(N));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,(*(,&! \"\"\"\"\"%\"pGF(F(,(%\"NGF'!\"#F(%\"nGF(F(-%\"KG6#,&F+F(\"\"#F(F(F'*& ,.%\"xGF(F)F2F-F(!\"$F(*&F)F(F+F(F(F+F,F(-F/6#,&F+F(F(F(F(F'*&,(F5F(F+ F'F'F(F(-F/6#F+F(F(\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 " " }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 10 "Koepf 7.15" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 247 "for dd from 2 to 5 do\n print(`recursion for d`= dd);\n rec := (sumrecursion((-1)^k*binomial(n,k)*binomial(dd*k,n),k,s (n)));\n print(rec);\n fn := subs(d_=dd, n -> (-d_)^n);\n print(`Ch eck at s`(n)=eval(fn),`: `,expand(eval(subs(s=fn,rec))));\nod:" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/%0recursion~for~dG\"\"#" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#/,&-%\"sG6#,&%\"nG\"\"\"F*F*F*-F&6#F)\"\"#\"\"! " }}{PARA 11 "" 1 "" {XPPMATH 20 "6%/-%+Check~at~sG6#%\"nG:F&6\"6$%)op eratorG%&arrowGF))!\"#9$F)F)%%:~~~G/\"\"!F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%0recursion~for~dG\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,(*&,&%\"nG\"\"#\"\"$\"\"\"F*-%\"sG6#,&F'F*F(F*F*F(*&,&F'\"\"& \"\"(F*F*-F,6#,&F'F*F*F*F*F)*&F5F*-F,6#F'F*\"\"*\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%/-%+Check~at~sG6#%\"nG:F&6\"6$%)operatorG%&arrowGF ))!\"$9$F)F)%%:~~~G/\"\"!F2" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/%0recu rsion~for~dG\"\"%" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,***,&\"\"(\"\" \"%\"nG\"\"$F(,&\"\"%F(F)F*F(,&F)F*\"\")F(F(-%\"sG6#,&F)F(F*F(F(F**(F+ F(,(*$F)\"\"#\"#PF)\"$!=\"$=#F(F(-F06#,&F)F(F6F(F(F,*(F\"&>H&F'\"'z-5\"&-.(F*F*-F66#,&F'F*F(F*F *\"#D*,F-F*FDF*FQF*,*FJ\"$_\"F>\"%)4\"F'\"%PC\"%B;F*F*-F66#,&F'F*F*F*F *\"$D\"*0F&F*F-F*F0F*FDF*FQF*FenF*-F66#F'F*\"$D'\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%/-%+Check~at~sG6#%\"nG:F&6\"6$%)operatorG%&arrowGF ))!\"&9$F)F)%%:~~~G/\"\"!F2" }}}{EXCHG {PARA 11 "" 1 "" {TEXT -1 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 13 "Koepf 7.19(d)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 56 "closedform(binomial(-1/4,k)^2*binomial(-1/4,n-k) ^2,k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%*factorialG6#,$%\"nG\" \"#\"\"$)\"\"%F(!\"$-F%6#F(!\"'" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 13 "Koepf 7.19(e)" }}{PARA 0 "" 0 "" {TEXT -1 75 "This turned out to b e much more tedious than I ever imagined it would be..." }}{PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 121 "Fnk := hyperterm([-n,1-a-n,1-b-n],[a,b],1,k); \nFn := hypergeom([-n,1-a-n,1-b-n],[a,b],1);\nrec := sumrecursion(Fnk, k,s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FnkG*.-%+pochhammerG6$, $%\"nG!\"\"%\"kG\"\"\"-F'6$,(F-F-%\"aGF+F*F+F,F--F'6$,(F-F-%\"bGF+F*F+ F,F--F'6$F1F,F+-F'6$F5F,F+-%*factorialG6#F,F+" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#FnG-%*hypergeomG6%7%,$%\"nG!\"\",(\"\"\"F-%\"bGF+F*F +,(F-F-%\"aGF+F*F+7$F0F.F-" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$recG/ ,&*,,&%\"nG\"\"\"%\"bG\"\"#F*,&F)F*%\"aGF,F*,(F)F*F.F*F+F*F*,*F)F*!\" \"F*F.F*F+F*F*-%\"sG6#,&F)F*F,F*F*F**,,&F)F*F*F*F*,*F)\"\"$F,F*F.F,F+F ,F*,(F.F,F)F9F+F,F*,*F)F9F+F,!\"#F*F.F,F*-F36#F)F*F*\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 173 "It only involves s(n) and s(n+2), so it' s just as easy to solve as a first order recursion would be. But Mapl e doesn't see that, so I aborted this computation after awhile." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rsolve(rec,s(n));" }}{PARA 7 "" 1 " " {TEXT -1 32 "Warning, computation interrupted" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 117 "Let's transform it via n=2*N (for even n), t(N)=s(2 N).\nThen t(N+1)=s(2N+2) and it's a first order recursion for t(N)." } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "s_even := closedform(subs(n=2*N,Fn k),k,N);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%'s_evenG*8-%*factorialG6 #,$%\"NG\"\"#\"\"\")\"\"%F*!\"\"-%+pochhammerG6$,(#F,\"\"$F,%\"bGF4%\" aGF4F*F,-F16$,&F7F4F6F4F*F,-F16$,(#F/F5F,F6F4F7F4F*F,-F16$F6F*F/-F16$F 7F*F/-F16$,&F7#F,F+F6FFF*F/-F16$,(#F/F+F,F6FFF7FFF*F/)!#FF*F,-F'6#F*F/ " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 144 "Using Koepf Exercise 1.3, th is simplifies to the following (I found no built-in routine that will \+ do this automatically; this was done by hand):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 123 "s_even2 := (-2)^(n/2) * (n-1)!/(2^((n-2)/2)*((n-2)/2 )!) * pochhammer(a+b+n-1,n/2) / (pochhammer(a,n/2)*pochhammer(b,n/2)); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%(s_even2G*0)!\"#,$%\"nG#\"\"\" \"\"#F+-%*factorialG6#,&F)F+!\"\"F+F+)F,,&F)F*F1F+F1-F.6#F3F1-%+pochha mmerG6$,*F)F+F1F+%\"aGF+%\"bGF+F(F+-F76$F:F(F1-F76$F;F(F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Verify that s_even, s_even2, agree:" } {MPLTEXT 1 0 61 "'simplify(subs(N=nn,s_even)-subs(n=2*nn,s_even2))'$'n n'=1..5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'\"\"!F#F#F#F#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Similarly for odd terms, do n=2N+1." }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "s_odd:=closedform(subs(n=2*N+1,Fnk) ,k,N);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&s_oddG*4-%*factorialG6#% \"NG\"\"\"-%+pochhammerG6$,(%\"aG#F*\"\"$#F*\"\"#F*%\"bGF0F)F*-F,6$,(# F*\"\"'F*F4F0F/F0F)F*-F,6$,(F/F0#\"\"&F9F*F4F0F)F*-F,6$,&F4F*F2F*F)!\" \"-F,6$,&F/F*F2F*F)FB-F,6$,(F/F2F2F*F4F2F)FB-F,6$,&F/F2F4F2F)FB)!#FF)F *" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 318 "For odd n, there is a catch --- this answer is absolutely wrong. It should be identically 0. Ther e is a singularity of some sort that the program didn't catch.\nThe se ries is terminating because the upper parameter -n results in pochhamm er(-n,k)=0 for k>=n, so let's compute it directly by summing Fnk(n,k) \+ over k=0..n:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "Fn_ := proc(nn)\n local kk;\n fac tor(sum('simpcomb(subs(n=nn,k=kk,Fnk))', kk=0..nn));\nend:" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 39 "and now evaluate it for n from 0 to 10:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "for nn from 0 to 10 do FN[nn] := \+ Fn_(nn) od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"!%*undefin edG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"#,$*(,(%\"bG\"\"\"F,F,%\"aGF,F, F-!\"\"F+F.!\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"$\"\"! " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"%,$*.,(%\"aG\"\"\"%\" bGF,F'F,F,,(F+F,F-F,\"\"$F,F,,&F,F,F+F,!\"\"F+F1F-F1,&F,F,F-F,F1\"#7" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"&\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"',$*4,(%\"aG\"\"\"\"\"(F,%\"bGF,F,,(F +F,F'F,F.F,F,,(F+F,\"\"&F,F.F,F,F+!\"\",&F,F,F+F,F2,&F+F,\"\"#F,F2F.F2 ,&F,F,F.F,F2,&F.F,F5F,F2!$?\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#F NG6#\"\"(\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"),$*:,( %\"aG\"\"\"\"#5F,%\"bGF,F,,(F+F,\"\"*F,F.F,F,,(F+F,F'F,F.F,F,,(F+F,\" \"(F,F.F,F,F+!\"\",&F,F,F+F,F4,&F+F,\"\"#F,F4,&\"\"$F,F+F,F4F.F4,&F,F, F.F,F4,&F.F,F7F,F4,&F9F,F.F,F4\"%!o\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"\"*\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#FNG6#\"# 5,$*@,(%\"aG\"\"\"\"\"*F,%\"bGF,F,,(F+F,\"#8F,F.F,F,,(F+F,\"#7F,F.F,F, ,(F+F,\"#6F,F.F,F,,(F+F,F'F,F.F,F,,&F,F,F+F,!\"\",&F+F,\"\"#F,F7,&\"\" $F,F+F,F7,&F+F,\"\"%F,F7,&F,F,F.F,F7,&F.F,F9F,F7,&F;F,F.F,F7,&F.F,F=F, F7F.F7F+F7!&S-$" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 208 "Empirically, \+ when n is odd, the sum is 0. To prove it, we have the recursion above relating s(n) to s(n+2); since it's 0 for n=1, it's 0 for n=3,5,7,9,. .. by iterating the recursion. Now we consider even n." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "lcoeff(FN[10]);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#!&S-$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "'ifactor(lcoeff(FN[2*nn+2])/lcoeff(FN[2*nn]))'$'nn'=0 ..4;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6',$-%!G6#\"\"#!\"\",$*&F$\"\"\" -F%6#\"\"$F+F(,$*&F$F+-F%6#\"\"&F+F(,$*&F$F+-F%6#\"\"(F+F(,$*&F$F+F,F' F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "Empirically, when n=2N is \+ even, it is given by the formula above called s_even2." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 98 "Now check whether this direct computation agrees with the automatically discovered formula s_even:" }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 49 "'simplify(FN[2*nn]-subs(N=nn,s_even))'$'nn'= 1..5;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6'\"\"!F#F#F#F#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 10 "Koepf 7.21" }}{PARA 0 "" 0 "" {TEXT -1 129 "This is like the ha ndout for Koepf problem 4.7 done in class 10/29/99. It's almost the s ame except for the functions plugged in." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "sumrecursion(binomial(n-k,k)*x^k,k=0..n/2,s(n));" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/,(-%\"sG6#,&%\"nG\"\"\"\"\"#F*!\"\"-F &6#,&F)F*F*F*F**&%\"xGF*-F&6#F)F*F*\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 66 "sumrecursion(binomial(n+1,2*k+1)*(1+4*x)^k / 2^n, k=0 ..n/2, s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,(-%\"sG6#,&%\"nG\" \"\"\"\"#F*!\"\"-F&6#,&F)F*F*F*F**&%\"xGF*-F&6#F)F*F*\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "The recursions are the same! Check initi al conditions." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 108 "f1 := n \+ -> sum(binomial(n-k,k)*x^k,k=0..n/2);\nf2 := n -> sum(binomial(n+1,2*k +1)*(1+4*x)^k / 2^n, k=0..n/2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%# f1G:6#%\"nG6\"6$%)operatorG%&arrowGF(-%$sumG6$*&-%)binomialG6$,&9$\"\" \"%\"kG!\"\"F6F5)%\"xGF6F5/F6;\"\"!,$F4#F5\"\"#F(F(" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#f2G:6#%\"nG6\"6$%)operatorG%&arrowGF(-%$sumG6$*(-% )binomialG6$,&9$\"\"\"F5F5,&%\"kG\"\"#F5F5F5),&F5F5%\"xG\"\"%F7F5)F8F4 !\"\"/F7;\"\"!,$F4#F5F8F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "f1(0)=f2(0), f1(1)=f2(1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$/\"\" \"F$F#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 103 "That's all that's nece ssary. Check it for more. The variable nn was already set, so we mus t unset it." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "nn;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#6" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "nn := 'nn';" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#nnGF$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "nn;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#nnG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "'f1 (nn)=f2(nn)'$nn=0..5;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6(/\"\"\"F$F#/, &F$F$%\"xGF$F&/,&F$F$F'\"\"#F)/,(F$F$F'\"\"$*$F'F*F$,(#\"#:\"#;F$F'#\" \"&F**$,&F$F$F'\"\"%F*#F$F2/,(F$F$F'F7F.F-,(#\"#8F2F$F'F3F5#F-F2" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "'f1(nn)=expand(f2(nn))'$nn=0 ..5;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6(/\"\"\"F$F#/,&F$F$%\"xGF$F&/,& F$F$F'\"\"#F)/,(F$F$F'\"\"$*$F'F*F$F,/,(F$F$F'\"\"%F.F-F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 18 "Fibonacci numbers:" }}{PARA 0 "" 0 "" {TEXT -1 51 "This sum at x=1 gives the Fibonacci numbers. Thus," }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "Sumtohyper(binomial(n-k,k)*x^k,k); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%*HypergeomG6%7$,$%\"nG#!\"\"\"\" #,&#\"\"\"F+F.F(F)7#,$F(F*,$%\"xG!\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g1 := subs(Hypergeom=hypergeom,x=1,\");" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#g1G-%*hypergeomG6%7$,$%\"nG#!\"\"\"\"#,&#\"\" \"F-F0F*F+7#,$F*F,!\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "' evalf(subs(n=nn,g1))'$nn=1..6;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6($\"+ ++++5!\"*$\"+++++?F%$\"+++++IF%$\"+++++]F%$\"+++++!)F%$\"+++++8!\")" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "Sumtohyper(binomial(n+1,2* k+1)*(1+4*x)^k / 2^n, k);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(,&%\"nG \"\"\"F&F&F&)\"\"#,$F%!\"\"F&-%*HypergeomG6%7$,$F%#F*F(,&#F&F(F&F%F07# #\"\"$F(,&F&F&%\"xG\"\"%F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "g2 := subs(Hypergeom=hypergeom,x=1,\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#g2G*(,&%\"nG\"\"\"F(F(F()\"\"#,$F'!\"\"F(-%*hypergeo mG6%7$,$F'#F,F*,&#F(F*F(F'F27##\"\"$F*\"\"&F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "'evalf(subs(n=nn,g2))'$nn=1..6;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6($\"+++++5!\"*$\"+++++?F%$\"+++++IF%$\"+++++]F%$\"+ ,+++!)F%$\"+++++8!\")" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 3 "" 0 "" {TEXT -1 13 "Koepf 7.24(b)" }}{PARA 0 "" 0 " " {TEXT -1 27 "We may write the product as" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 85 "Sum(Sum(Hyperterm([a],[b],x,k)*Hyperterm([a],[b],-x,m ),k=0..infinity),m=0..infinity);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-% $SumG6$-F$6$*&-%*HypertermG6&7#%\"aG7#%\"bG%\"xG%\"kG\"\"\"-F*6&F,F.,$ F0!\"\"%\"mGF2/F1;\"\"!%)infinityG/F7F9" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 54 "and letting n = m+k, we pull out the factor x^n to get" } }{PARA 0 "> " 0 "" {MPLTEXT 1 0 84 "Sum(Sum(Hyperterm([a],[b],1,k)*Hyp erterm([a],[b],-1,n-k),k=0..n)*x^n,n=0..infinity);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#-%$SumG6$*&-F$6$*&-%*HypertermG6&7#%\"aG7#%\"bG\"\"\" %\"kGF1-F+6&F-F/!\"\",&%\"nGF1F2F5F1/F2;\"\"!F7F1)%\"xGF7F1/F7;F:%)inf inityG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 48 "Now find an expression \+ for the inside summation." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "sumrec ursion(hyperterm([a],[b],1,k)*hyperterm([a],[b],-1,n-k),k=0..n,s(n)); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*,,&%\"nG\"\"\"\"\"#F(F(,&F'F(% \"bGF)F(,(F+F(F'F(F(F(F(,&F+F(F'F(F(-%\"sG6#F&F(!\"\"*(,&%\"aGF)F'F(F( ,(F4!\"#F+F)F'F(F(-F/6#F'F(F(\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 223 "Once again, odd and even are different cases! We can tell fro m the definition of (b) that it is an even function of x, so the odd t erms all have coefficient 0. Thus, we rewrite the product again using only even exponents:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 92 "Sum(Sum(Hy perterm([a],[b],1,k)*Hyperterm([a],[b],-1,2*n-k),k=0..2*n)*x^(2*n),n=0 ..infinity);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%$SumG6$*&-F$6$*&-%*H ypertermG6&7#%\"aG7#%\"bG\"\"\"%\"kGF1-F+6&F-F/!\"\",&%\"nG\"\"#F2F5F1 /F2;\"\"!,$F7F8F1)%\"xGF " 0 "" {MPLTEXT 1 0 72 "sumrecursion(hyperterm([a],[b],1,k)*hyperterm([a ],[b],-1,2*n-k),k,s(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*,,&%\" nG\"\"\"F(F(F(,&F'\"\"#%\"bGF(F(,&F+F(F'F(F(,(F'F*F(F(F+F(F(-%\"sG6#F& F(!\"\"*(,&F'F(%\"aGF(F(,(F4F1F+F(F'F(F(-F/6#F'F(F(\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 47 "That's better, now it will be able to sol ve it." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 90 "insidesum := closedform(h yperterm([a],[b],1,k)*hyperterm([a],[b],-1,2*n-k),k,n) * x^(2*n);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%*insidesumG*2-%+pochhammerG6$%\"aG% \"nG\"\"\"-F'6$,&F)!\"\"%\"bGF+F*F+-F'6$,$F0#F+\"\"#F*F/-F'6$F0F*F/-F' 6$,&F4F+F0F4F*F/)#F+\"\"%F*F+-%*factorialG6#F*F/)%\"xG,$F*F5F+" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "Sumtohyper(insidesum,n);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%*HypergeomG6%7$%\"aG,&F'!\"\"%\"bG\" \"\"7%,&#F+\"\"#F+F*F.,$F*F.F*,$*$%\"xGF/#F+\"\"%" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 13 }{VIEWOPTS 1 1 0 1 1 1803 }