{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 "" 0 1 0 0 0 0 0 0 0 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 "Courier" 
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 "" 2 6 1 {CSTYLE "" -1 
-1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 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 "" 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 }}
{SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT 256 46 "/home/m262f99/KOEPF/works
heetsV.4/hw4ansmB.mws" }{MPLTEXT 1 0 0 "" }}{PARA 256 "" 0 "" {TEXT 
257 103 "Math 262a, Fall 1999, Glenn Tesler\nHomework 4\nAlternate sol
ution of Koepf 7.21 using Zeilberger's EKHAD" }}}{EXCHG {PARA 3 "" 0 "
" {TEXT -1 12 "Koepf # 7.21" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 32 "For nonnegative integer n, prove" }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 98 "Sum(binomial(n-k,k)*x^k,k=0..floor(n/2))=Sum(binomi
al(n+1,2*k+1)*(1+4*x)^k / 2^n,k=0..floor(n/2));" }}{PARA 12 "" 1 "" 
{XPPMATH 20 "6#/-%$SumG6$*&-%)binomialG6$,&%\"nG\"\"\"%\"kG!\"\"F.F-)%
\"xGF.F-/F.;\"\"!-%&floorG6#,$F,#F-\"\"#-F%6$*(-F)6$,&F,F-F-F-,&F.F:F-
F-F-),&F-F-F1\"\"%F.F-)F:F,F/F2" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
380 "The bounds on both sides are the natural bounds, so we may sum k=
-infinity..infinity.\nWe will show that both sides satisfy the same re
cursion and initial conditions.\n(It is NOT necessary that the algorit
hm discover the same recursion for both sides, even if they are equal;
 later we'll learn about noncommutative LCM's and GCD's and the Euclid
ean algorithm for dealing with that.)" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 11 "read EKHAD;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%8Vers
ion~of~Feb~25,~1999G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%hnThis~versio
n~is~much~faster~than~previous~versions,~thanks~toG" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#%Sa~remark~of~Frederic~Chyzak.~We~thank~him~SO~MUCH!G
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%DThe~penultimate~version,~Feb.~19
97,G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%W~corrected~a~subtle~bug~disc
overed~by~Helmut~ProdingerG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%enPrev
ious~versions~benefited~from~comments~by~Paula~Cohen,~G" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#%?Lyle~Ramshaw,~and~Bob~Sulanke.G" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#%IThis~is~EKHAD,~One~of~the~Maple~packagesG" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#%7accompanying~the~book~G" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#%(~\"A=B\"~G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#%M~(published~by~A.K.~Peters,~Welesley,~1996)~G" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#%V~by~Marko~Petkovsek,~Herb~Wilf,~and~Doron~Zeilberger.
G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%QThe~most~current~version~is~ava
ilable~on~WWW~at:G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%H~http://www.ma
th.temple.edu/|irzeilberg~.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%[oInf
ormation~about~the~book,~and~how~to~order~it,~can~be~found~inG" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#%Shttp://www.central.cis.upenn.edu/|ir
wilf/AeqB.html~.G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%VPlease~report~a
ll~bugs~to:~zeilberg@math.temple.edu~.G" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#%inAll~bugs~or~other~comments~used~will~be~acknowledged~in~futur
eG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%*versions.G" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#%YFor~general~help,~and~a~list~of~the~available~funct
ions,G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%jn~type~\"ezra();\".~For~sp
ecific~help~type~\"ezra(procedure_name)\"~G" }}}{EXCHG {PARA 0 "> " 0 
"" {MPLTEXT 1 0 55 "F1 := (n,k)->binomial(n-k,k)*x^k;\nzeilpap(F1(n,k)
,k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G:6$%\"nG%\"kG6\"6$%)op
eratorG%&arrowGF)*&-%)binomialG6$,&9$\"\"\"9%!\"\"F4F3)%\"xGF4F3F)F)" 
}}{PARA 6 "" 1 "" {TEXT -1 123 "\nA PROOF OF A RECURRENCE\n\nBy Shalos
h B. Ekhad, Temple University, ekhad@math.temple.edu\n\nTheorem:Let   \+
F(n,k)   be given by" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%)binomialG
6$,&%\"nG\"\"\"%\"kG!\"\"F*F))%\"xGF*F)" }}{PARA 6 "" 1 "" {TEXT -1 
131 "\nand let   SUM(n)   be the sum of   F(n,k)    with\nrespect to  \+
 k   .\n\nSUM(n)    satisfies the following linear recurrence equation
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&%\"xG\"\"\"-%$SUMG6#%\"nGF&!\"
\"-F(6#,&F*F&F&F&F+-F(6#,&F*F&\"\"#F&F&" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#%$=0.G" }}{PARA 6 "" 1 "" {TEXT -1 43 "\nPROOF: We cleverly cons
truct   G(n,k)   :=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*.,(%\"nG!\"\"F
&\"\"\"%\"kGF'F'F(F',(F(\"\"#F%F&F&F'F&,(F%F&!\"#F'F(F*F&-%)binomialG6
$,&F%F'F(F&F(F')%\"xGF(F'" }}{PARA 6 "" 1 "" {TEXT -1 20 "with the mot
ive that" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&%\"xG\"\"\"-%\"FG6$%\"
nG%\"kGF&!\"\"-F(6$,&F*F&F&F&F+F,-F(6$,&F*F&\"\"#F&F+F&" }}{PARA 6 "" 
1 "" {TEXT -1 96 "=   G(n,k+1)-G(n,k)   (check!)\n\nand the theorem fo
llows upon summing with respect to   k   .QED." }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 73 "F2 := (n,k) -> binomial(n+1,2*k+1)*(1+4*x)^k /
 2^n;\nzeilpap(F2(n,k),k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F2G
:6$%\"nG%\"kG6\"6$%)operatorG%&arrowGF)*(-%)binomialG6$,&9$\"\"\"F3F3,
&9%\"\"#F3F3F3),&F3F3%\"xG\"\"%F5F3)F6F2!\"\"F)F)" }}{PARA 6 "" 1 "" 
{TEXT -1 123 "\nA PROOF OF A RECURRENCE\n\nBy Shalosh B. Ekhad, Temple
 University, ekhad@math.temple.edu\n\nTheorem:Let   F(n,k)   be given \+
by" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*(-%)binomialG6$,&%\"nG\"\"\"F)F
),&%\"kG\"\"#F)F)F)),&F)F)%\"xG\"\"%F+F))F,F(!\"\"" }}{PARA 6 "" 1 "" 
{TEXT -1 131 "\nand let   SUM(n)   be the sum of   F(n,k)    with\nres
pect to   k   .\n\nSUM(n)    satisfies the following linear recurrence
 equation" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,(*&%\"xG\"\"\"-%$SUMG6#%
\"nGF&F&-F(6#,&F*F&F&F&F&-F(6#,&F*F&\"\"#F&!\"\"" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#%$=0.G" }}{PARA 6 "" 1 "" {TEXT -1 43 "\nPROOF: We clev
erly construct   G(n,k)   :=" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*0%
\"kG\"\"\",&F%\"\"#F&F&F&,(F%F(%\"nG!\"\"F+F&F+,(F*F+!\"#F&F%F(F+-%)bi
nomialG6$,&F*F&F&F&F'F&),&F&F&%\"xG\"\"%F%F&)F(F*F+#F&F(" }}{PARA 6 "
" 1 "" {TEXT -1 20 "with the motive that" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#,(*&%\"xG\"\"\"-%\"FG6$%\"nG%\"kGF&F&-F(6$,&F*F&F&F&F+F&-F(6$,&F
*F&\"\"#F&F+!\"\"" }}{PARA 6 "" 1 "" {TEXT -1 96 "=   G(n,k+1)-G(n,k) \+
  (check!)\n\nand the theorem follows upon summing with respect to   k
   .QED." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 385 "Notice both sides sa
tisfy the same recursion of order 2!  The coefficient of SUM(n+2) is 1
, so there are no singularities in this equation.  Thus, as long as bo
th sums agree for n=0 and n=1 (i.e., the first 2 values), iterating th
e recursion will make all future values equal as well.  Here we check \+
f1(0),...,f1(10) to demonstrate this (but to prove it, only f1(0), f1(
1) are needed):" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 120 "f1 := n -> expand(sum(F1(n,k),k=0..n/2));\n         \+
  # maple truncates n/2 to floor(n/2) on its own\n'f1(nn)'$'nn'=0..10;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G:6#%\"nG6\"6$%)operatorG%&ar
rowGF(-%'expandG6#-%$sumG6$-%#F1G6$9$%\"kG/F6;\"\"!,$F5#\"\"\"\"\"#F(F
(" }}{PARA 12 "" 1 "" {XPPMATH 20 "6-\"\"\"F#,&F#F#%\"xGF#,&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*\"#5F0F,,,F#F#F%\"\"(F*\"#:F0F2*$F%F,F#,,F#F#F%\"\")F*\"#@F0
\"#?F6F.,.F#F#F%\"\"*F*\"#GF0\"#NF6F5*$F%F.F#" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 20 "And the same for f2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 
0 62 "f2 := n -> expand(sum(F2(n,k),k=0..n/2));\n'f2(nn)'$'nn'=0..10;
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f2G:6#%\"nG6\"6$%)operatorG%&ar
rowGF(-%'expandG6#-%$sumG6$-%#F2G6$9$%\"kG/F6;\"\"!,$F5#\"\"\"\"\"#F(F
(" }}{PARA 12 "" 1 "" {XPPMATH 20 "6-\"\"\"F#,&F#F#%\"xGF#,&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*\"#5F0F,,,F#F#F%\"\"(F*\"#:F0F2*$F%F,F#,,F#F#F%\"\")F*\"#@F0
\"#?F6F.,.F#F#F%\"\"*F*\"#GF0\"#NF6F5*$F%F.F#" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 44 "And we can have them compared directly, too:" }}{PARA 
0 "> " 0 "" {MPLTEXT 1 0 33 "'expand(f1(nn)-f2(nn))'$nn=0..10;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"!F#F#F#F#F#F#F#F#F#F#" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 1 0" 103 }{VIEWOPTS 
1 1 0 1 1 1803 }