{VERSION 6 0 "IBM INTEL NT" "6.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 
1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 
0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "" -1 256 "" 1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 
257 "" 1 18 0 0 0 0 1 1 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 
0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 1 0 0 0 0 0 
0 0 0 0 }{CSTYLE "" -1 260 "" 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Error" -1 8 1 
{CSTYLE "" -1 -1 "Courier" 1 10 255 0 255 1 2 2 2 2 2 1 1 1 3 1 }1 1 
0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 
-1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 
0 1 }{PSTYLE "Maple Output" -1 12 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 
0 1 2 2 2 2 2 2 1 1 1 1 }1 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Author
" 0 19 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 
-1 8 8 0 0 0 0 0 0 -1 0 }{PSTYLE "Normal" -1 256 1 {CSTYLE "" -1 -1 "T
imes" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }
}
{SECT 0 {EXCHG {PARA 19 "" 0 "" {TEXT 256 97 "Formula (6.16) Revisited
:\nObtaining the Generating Function by a Holonomic Differential Equat
ion\n" }{TEXT 257 28 "(or: no \"tricks\" anymore...)" }}{PARA 19 "" 0 
"" {TEXT 260 32 "Folkmar Bornemann, March 9, 2007" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 60 "We apply Zeilberger's algorithm to the return prob
abilities " }{XPPEDIT 18 0 "p[k];" "6#&%\"pG6#%\"kG" }{TEXT -1 53 " to
 obtain a holonomic recurrence equation. (Writing " }{XPPEDIT 18 0 "a \+
= p[EW];" "6#/%\"aG&%\"pG6#%#EWG" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "
b = p[NS];" "6#/%\"bG&%\"pG6#%#NSG" }{TEXT -1 90 " for short.) This is
, once more, what we have done in the Maple session preceeding (6.14).
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 88 "rec:=sumtools[sumrecurs
ion](binomial(2*k,k)*binomial(k,j)^2*a^(2*j)*b^(2*(k-j)),j,p(k));" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$recG,(*.\"\"%\"\"\"),&%\"aGF(%\"bG!
\"\"\"\"#F(),&F+F(F,F(F.F(,&*&F.F(%\"kGF(F(F(F-F(,&*&F.F(F3F(F(\"\"$F-
F(-%\"pG6#,&F3F(F.F-F(F(**F.F(,&*$)F+F.F(F(*$)F,F.F(F(F()F1F.F(-F86#,&
F3F(F(F-F(F-*&-F86#F3F()F3F.F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
59 "\nNow, we depart and transform the holonomic recurrence for " }
{XPPEDIT 18 0 "p[k];" "6#&%\"pG6#%\"kG" }{TEXT -1 68 " into a holonomi
c differential equation for the generating function " }{XPPEDIT 18 0 "
E(x) = sum(p[k]*x^k,k = 0 .. infinity);" "6#/-%\"EG6#%\"xG-%$sumG6$*&&
%\"pG6#%\"kG\"\"\")F'F/F0/F/;\"\"!%)infinityG" }{TEXT -1 1 "." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 125 "dic:=gfun[rectodiffeq](\{re
c=0,p(0)=1,p(1)=2*(a^2+b^2)\},p(k),E(x)): deq:=remove(hastype,dic,`=`)
; ic:=select(hastype,dic,`=`);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$d
eqG<#,(*&,,*(\"#7\"\"\"%\"xGF+)%\"aG\"\"%F+F+**\"#CF+F,F+)%\"bG\"\"#F+
)F.F4F+!\"\"*(F*F+F,F+)F3F/F+F+*&F4F+F5F+F6*&F4F+F2F+F6F+-%\"EG6#F,F+F
+*&,.**\"#'*F+)F,F4F+F2F+F5F+F6*(\"#[F+FBF+F-F+F+*(FDF+FBF+F8F+F+*(\"#
;F+F,F+F5F+F6*(FGF+F,F+F2F+F6F+F+F+-%%diffG6$F;F,F+F+*&,.*(FGF+)F,\"\"
$F+F8F+F+**\"#KF+FOF+F2F+F5F+F6*(FGF+FOF+F-F+F+*(\"\")F+FBF+F2F+F6*(FU
F+FBF+F5F+F6F,F+F+-FJ6$F;-%\"$G6$F,F4F+F+" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#icG<$/--%\"DG6#%\"EG6#\"\"!,&*&\"\"#\"\"\")%\"aGF0F1
F1*&F0F1)%\"bGF0F1F1/-F+F,F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 42 "T
he differential equation degenerates for " }{XPPEDIT 18 0 "x = 0;" "6#
/%\"xG\"\"!" }{TEXT -1 24 ", but the initial value " }{XPPEDIT 18 0 "d
iff(E(0),x) = 2*(a^2+b^2);" "6#/-%%diffG6$-%\"EG6#\"\"!%\"xG*&\"\"#\"
\"\",&*$%\"aGF-F.*$%\"bGF-F.F." }{TEXT -1 54 " is by construction comp
atible with this degeneracies." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 
1 0 14 "subs(x=0,deq);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#,&*&,&*&\"
\"#\"\"\")%\"aGF(F)!\"\"*&F(F))%\"bGF(F)F,F)-%\"EG6#\"\"!F)F)-%%diffG6
$F0F3F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 66 "The second order holon
omic differential equation is easily solved " }{TEXT 259 11 "numerical
ly" }{TEXT -1 32 " for the desired expected value " }{XPPEDIT 18 0 "E;
" "6#%\"EG" }{TEXT -1 46 " of the number of visits by integrating it t
o " }{XPPEDIT 18 0 "x = 1;" "6#/%\"xG\"\"\"" }{TEXT -1 213 ". This yie
lds a further numerical method to solve Problem 6 in less than a secon
d (see the accompanying Matlab routine 'problem6_by_diffeq.m'). Howeve
r, we could courageously try to find the solution  to it using " }
{TEXT 258 8 "symbolic" }{TEXT -1 9 " methods." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 38 "sol:=DEtools[hypergeomsols](deq,E(x));" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#>%$solG7$*&,**(\"\"%\"\"\"%\"xGF*)%\"aG\"\"#
F*F***\"\")F*F+F*%\"bGF*F-F*!\"\"*(F)F*F+F*)F1F.F*F*F*F2#F2F.-%*Legend
rePG6$F5*&,***\"#CF*F+F*F1F*F-F*F**(F)F*F+F*F,F*F**(F)F*F+F*F4F*F*F*F2
F*F'F2F**&F'F5-%*LegendreQGF8F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
103 "Because of the degeneracy, there is a one-dimensional subspace of
 solutions that have finite values at " }{XPPEDIT 18 0 "x = 0;" "6#/%
\"xG\"\"!" }{TEXT -1 57 ". Lets check the given basis elements for tha
t property. " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "eval(subs(x
=0,sol[1]));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#^#!\"\"" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "eval(subs(x=0,sol[2]));" }}{PARA 8 
"" 1 "" {TEXT -1 58 "Error, (in LegendreQ) numeric exception: division
 by zero\n" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 129 "In half of the run
s (Maple behaves non-deterministic here), we are lucky and the first e
lement of the given basis, involving the " }{XPPEDIT 18 0 "LegendreP;
" "6#%*LegendrePG" }{TEXT -1 24 " function, is finite at " }{XPPEDIT 
18 0 "x = 0;" "6#/%\"xG\"\"!" }{TEXT -1 51 ". (Otherwise restart and r
epeat.) We normalize for " }{XPPEDIT 18 0 "E(0) = 1.;" "6#/-%\"EG6#\"
\"!-%&FloatG6$\"\"\"F'" }{TEXT -1 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 30 "sol[1]/eval(subs(x=0,sol[1]));" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#*(,**(\"\"%\"\"\"%\"xGF')%\"aG\"\"#F'F'**\"\")F'F(F'%\"
bGF'F*F'!\"\"*(F&F'F(F')F.F+F'F'F'F/#F/F+-%*LegendrePG6$F2*&,***\"#CF'
F(F'F.F'F*F'F'*(F&F'F(F'F)F'F'*(F&F'F(F'F1F'F'F'F/F'F$F/F'^#F'F'" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 56 "Cross-check that the differential \+
equation is satisfied." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "s
implify(subs(E(x)=%,deq));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#\"\"!
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 135 "The expression that we have \+
obtained already qualifies as a \"closed\" form solution. However, we \+
can even do better by recognizing that " }{XPPEDIT 18 0 "LegendreP(-1/
2,z);" "6#-%*LegendrePG6$,$*&\"\"\"F(\"\"#!\"\"F*%\"zG" }{TEXT -1 64 "
 is related to the complete elliptic integral of the first kind " }
{XPPEDIT 18 0 "K;" "6#%\"KG" }{TEXT -1 59 " (see Abramowitz/Stegun \+
\2478.13). The desired expected value " }{XPPEDIT 18 0 "E;" "6#%\"EG" 
}{TEXT -1 54 " of the number of visits is obtained by evaluating at " 
}{XPPEDIT 18 0 "x = 1;" "6#/%\"xG\"\"\"" }{TEXT -1 1 "." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 73 "E=simplify(subs(x=1,convert(%%,Elli
pticK))) assuming 0<=b,b<=a,a-b<=1/2; " }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#/%\"EG,$**\"\"#\"\"\",*F(F(*&\"\"%F()%\"aGF'F(!\"\"*(\"\")F(%\"b
GF(F-F(F(*&F+F()F1F'F(F.#F.F'%#PiGF.-%*EllipticKG6#,$**F+F(F)F4F1#F(F'
F-F;F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 149 "This is exactly formula (6.16) in \2476.
5, that we had previously obtained by a \"trick\" due to Herb Wilf. Ou
r approach here is probably more systematic." }}}}{MARK "1 0 0" 4 }
{VIEWOPTS 1 1 0 3 2 1804 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }