{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 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 
"" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 0 0 0 2 0 0 0 0 0 0 0 }
{CSTYLE "" -1 261 "terminal" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "
" -1 262 "" 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 "Maple 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 "Author" 0 19 1 {CSTYLE "" 
-1 -1 "" 0 1 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 "R3 Font 0" -1 256 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 257 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 }{PSTYLE "" 0 258 1 {CSTYLE "" -1 
-1 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }
{PSTYLE "" 0 259 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 "" 0 260 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 "" 0 261 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 "" 0 262 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 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 261 47 "/home/m262f99/KOEPF/works
heetsV.4/hyperdemo.mws" }{MPLTEXT 1 0 0 "" }}{PARA 19 "" 0 "" {TEXT 
262 93 "Math 262a, Fall 1999, Glenn Tesler\nPolynomial/Hypergeometric \+
solutions of recurrences\n11/8/99" }}}{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 0 "" 0 "" {TEXT 256 9 "Example 1" }{TEXT -1 116 ". Polyno
mial solutions of a recurrence equation.\nSince  (n*(n+1)*(n+2,8))^2 -
 (n,8)*(n+8)*(n+9))^2 = 0, we must have" }}{PARA 259 "" 0 "" {TEXT -1 
45 "f(n) = pochhammer(n,8)^2 = (n(n+1)...(n+7))^2" }}{PARA 0 "" 0 "" 
{TEXT -1 16 "as a solution of" }}{PARA 260 "" 0 "" {TEXT -1 43 "(n(n+1
))^2 f(n+2) - ((n+8)(n+9))^2 f(n) = 0" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 57 "recpoly((n*(n+1))^2*f(n+2) - ((n+8)*(n+9))^2*f(n), f(
n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*4&%&deltaG6#\"\"!\"\"\"%\"nG
\"\"#,&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(F(F(F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 33 "delta_0 is an arbitrary constant." }{MPLTEXT 1 0 0 "" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT 257 12 "Example 2.  " }{TEXT -1 50 "Hyper
geometric solutions of a recurrence equation." }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 31 "f1 := hyperterm([a,b],[c],x,n);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#f1G*,-%+pochhammerG6$%\"aG%\"nG\"\"\"-F'6$%\"bGF*F+-
F'6$%\"cGF*!\"\")%\"xGF*F+-%*factorialG6#F*F2" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 28 "simpcomb(subs(n=n+2,f1)/f1);" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#*4,&%\"aG\"\"\"%\"nGF&F&,(F%F&F'F&F&F&F&,&%\"bGF&F'F&
F&,(F*F&F'F&F&F&F&,&%\"cGF&F'F&!\"\",(F-F&F'F&F&F&F.%\"xG\"\"#,&F'F&F&
F&F.,&F'F&F1F&F." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "eq := n
umer(\")*f(n) - denom(\")*f(n+2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>
%#eqG,&*.,&%\"aG\"\"\"%\"nGF)F),(F(F)F*F)F)F)F),&%\"bGF)F*F)F),(F-F)F*
F)F)F)F)%\"xG\"\"#-%\"fG6#F*F)F)*,,&%\"cGF)F*F)F),(F6F)F*F)F)F)F),&F*F
)F)F)F),&F*F)F0F)F)-F26#F9F)!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
58 "By construction, this is solved by the hypergeometric term" }}
{PARA 261 "" 0 "" {TEXT -1 14 "2F1(a,b;c;x)_n" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 28 "ratios := rechyper(eq,f(n));" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%'ratiosG<$,$*,%\"xG\"\"\",&%\"bGF)%\"nGF)F),&%\"aGF)F
,F)F),&F,F)F)F)!\"\",&%\"cGF)F,F)F0F0F'" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 107 "It doesn't return f(n), but rather the ratio f(n+1)/f(n)
.  Also, it found a SECOND hypergeometric solution:" }}{PARA 262 "" 0 
"" {TEXT -1 16 "2F1(a,b;c; -x)_n" }}{PARA 0 "" 0 "" {TEXT -1 37 "which
 in retrospect isn't surprising." }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 28 "ratiosk := subs(n=k,ratios):" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "product(ratiosk[1],k=0..n-1); produ
ct(ratiosk[2],k=0..n-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*2)%\"xG%
\"nG\"\"\"-%&GAMMAG6#,&%\"bGF'F&F'F'-F)6#,&%\"aGF'F&F'F'-F)6#,&F&F'F'F
'!\"\"-F)6#,&%\"cGF'F&F'F4-F)6#F,F4-F)6#F0F4-F)6#F8F'" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#*4)!\"\"%\"nG\"\"\")%\"xGF&F'-%&GAMMAG6#,&%\"bGF'F
&F'F'-F+6#,&%\"aGF'F&F'F'-F+6#,&F&F'F'F'F%-F+6#,&%\"cGF'F&F'F%-F+6#F.F
%-F+6#F2F%-F+6#F9F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 259 41 "Applicati
on to factorization of operators" }}{PARA 0 "" 0 "" {TEXT -1 1131 "Giv
en a root x0 in C of a polynomial f(x) over Q, then f(x)=g(x)*(x-x0) f
or some polynomial g(x) over C.\nIf the minimal polynomial of x0 over \+
Q is h(x), then f(x)=p(x)h(x) for some polynomial p(x) over Q.\n\nNow \+
consider a differential operator L = sum a_i(x) Dx^i, each a_i(x) in Q
(x), that annihilates a function f(x), or a recurrence operator that a
nnihilates a function f(n), etc.\n\nThe first order operator R = f(x) \+
Dx - f'(x) annihilates f(x) in the differential case, and R = f(n) En \+
- f(n+1) annihilates f(n) in the shift case. f is the analogue of a ro
ot x0 in an extension field; R is the analogue of the linear factor x-
x0. Using non-commutative right division of L by R we obtain a factori
zation L = G R, with G, R operators (over the extension, usually not o
ver Q(x)).\n\nThere is a minimal order operator H over Q(x) that annih
ilates f.  Using non-commutative right division of L by H gives an ope
rator P over Q(x) with L = P H.\n\nThere is software available for the
se divisions that we will use later.  Non-commutative factorization in
 general is only a partially solved problem, and I don't have anyone's
 software for it." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "L := s
ubs(f(n)=1,f(n+1)=En,f(n+2)=En^2,eq);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#>%\"LG,&*,,&%\"aG\"\"\"%\"nGF)F),(F(F)F*F)F)F)F),&%\"bGF)F*F)F),(F-
F)F*F)F)F)F)%\"xG\"\"#F)*,,&%\"cGF)F*F)F),(F3F)F*F)F)F)F),&F*F)F)F)F),
&F*F)F0F)F)%#EnGF0!\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "
R_op := En - ratios[1]; Rf := f(n+1) - ratios[1]*f(n);" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#>%%R_opG,&%#EnG\"\"\"*,%\"xGF',&%\"bGF'%\"nGF'F',&
%\"aGF'F,F'F',&F,F'F'F'!\"\",&%\"cGF'F,F'F0F'" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#RfG,&-%\"fG6#,&%\"nG\"\"\"F+F+F+*.%\"xGF+,&%\"bGF+F*
F+F+,&%\"aGF+F*F+F+F)!\"\",&%\"cGF+F*F+F2-F'6#F*F+F+" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 49 "G_op := A*En - B; GRf := A*subs(n=n+1,Rf)
 - B*Rf;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%G_opG,&*&%\"AG\"\"\"%#E
nGF(F(%\"BG!\"\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$GRfG,&*&%\"AG\"
\"\",&-%\"fG6#,&%\"nGF(\"\"#F(F(*.%\"xGF(,(%\"bGF(F.F(F(F(F(,(%\"aGF(F
.F(F(F(F(F-!\"\",(%\"cGF(F.F(F(F(F6-F+6#,&F.F(F(F(F(F(F(F(*&%\"BGF(,&F
9F(*.F1F(,&F3F(F.F(F(,&F5F(F.F(F(F;F6,&F8F(F.F(F6-F+6#F.F(F(F(F6" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 98 "fs := \{f(n),f(n+1),f(n+2)\}
: collect(GRf - eq, fs): coeffs(\",fs):\nsols := factor(solve(\{\"\},
\{A,B\}));" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%solsG<$/%\"AG,$**,&%
\"cG\"\"\"%\"nGF,F,,(F+F,F-F,F,F,F,,&F-F,F,F,F,,&F-F,\"\"#F,F,!\"\"/%
\"BG,$*,,(%\"aGF,F-F,F,F,F,,(%\"bGF,F-F,F,F,F,%\"xGF,F/F,F*F,F2" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "map(collect,factor(subs(sols
,G_op)),En,factor);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(,&%\"nG\"\"\"
F&F&F&,&%\"cGF&F%F&F&,&*(,&F%F&\"\"#F&F&,(F(F&F%F&F&F&F&%#EnGF&!\"\"*(
%\"xGF&,(%\"bGF&F%F&F&F&F&,(%\"aGF&F%F&F&F&F&F&F&" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 86 "The factored form of L obtained by using the first
 ratio to generate a right factor is" }{MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "factorL := \" * R_op;" }}{PARA 12 "
" 1 "" {XPPMATH 20 "6#>%(factorLG**,&%\"nG\"\"\"F(F(F(,&%\"cGF(F'F(F(,
&*(,&F'F(\"\"#F(F(,(F*F(F'F(F(F(F(%#EnGF(!\"\"*(%\"xGF(,(%\"bGF(F'F(F(
F(F(,(%\"aGF(F'F(F(F(F(F(F(,&F0F(*,F3F(,&F5F(F'F(F(,&F7F(F'F(F(F&F1F)F
1F(F(" }}}{EXCHG {PARA 258 "" 0 "" {TEXT -1 11 "Example 3. " }{TEXT 
260 42 "Failure to find a hypergeometric solution." }}}{EXCHG {PARA 0 
"" 0 "" {TEXT -1 154 "Now test the recurrence obtained on my handout \+
\"Creative telescoping for a triple integral\":\nThe sequence a(n) = b
inomial(n,n/2)^2 satisfies a recurrence:" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 49 "rechyper(16*(n+1)^2*a(n) - (n+2)^2*a(n+2), a(n));" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#<\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 275 "There's no hypergeometric solutions because binomial(n,n/2) is
 2-fold hypergeometric, not 1-fold. This can be detected automatically
, but not with this software.  (Even that can fail if there's no k-fol
d solutions for any k, which is possible.)  Substitute n=2m, b(m)=a(n/
2):" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "r
echyper(16*(2*m+1)^2 * b(m) - (2*m+2)^2 * b(m+1), b(m));" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#<#,$*&,&%\"mG\"\"#\"\"\"F)F(,&F'F)F)F)!\"#\"\"%
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "subs(m=m0,\"[1]): produ
ct(\",m0=0..m-1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*,)\"\"%%\"mG\"\"
\")\"\"#F&F)-%&GAMMAG6#,&F&F'#F'F)F'F)-F+6#,&F&F'F'F'!\"#%#PiG!\"\"" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "an1 := simplify(subs(m=n/2
,\"));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$an1G**)\"\"#,$%\"nGF'\"\"
\"-%&GAMMAG6#,&F)#F*F'F/F*F'-F,6#,&F)F/F*F*!\"#%#PiG!\"\"" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 210 "This is the same as binomial(n,n/2)^2 (i
dentifying binomial coefficients with their def. in terms of factorial
s, and factorials in terms of Gamma functions, so that non-nonnegative
 integer arguments are valid)." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "s
implify( an1 / binomial(n,n/2)^2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#
\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "23 0 \+
0" 244 }{VIEWOPTS 1 1 0 1 1 1803 }