{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 "" 20 256 "" 1 14 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" 20 
257 "" 1 14 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "terminal" 0 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 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 "Tex
t 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 "" 11 
256 1 {CSTYLE "" -1 -1 "" 1 14 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 "" 11 257 1 {CSTYLE "" -1 -1 "" 1 14 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 "" 11 
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 "" 3 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 "R3 Font
 0" -1 260 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 261 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 258 36 "/home/m262f99/A=B/Maple/k
oepf4.7.mws" }{MPLTEXT 1 0 0 "" }}{PARA 259 "" 0 "" {TEXT 259 122 "Mat
h 262a, Fall 1999, Glenn Tesler\nShowing sums are equal, without being
 able to evaluate the sums in closed form\n10/25/99" }}}{EXCHG {PARA 
3 "" 0 "" {TEXT -1 11 "Koepf # 4.7" }{MPLTEXT 1 0 0 "" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 32 "For nonnegative integer n, prove" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 72 "Sum(binomial(n,k)^3,k=0..n)=Sum(bin
omial(n,k)^2*binomial(2*k,n),k=0..n);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#/-%$SumG6$*$-%)binomialG6$%\"nG%\"kG\"\"$/F,;\"\"!F+-F%6$*&F(\"\"#-
F)6$,$F,F4F+\"\"\"F." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 377 "The boun
ds on both sums are the natural bounds, so we may sum k=-infinity..inf
inity.\nWe will show that both sums satisfy the same recursion and ini
tial conditions.\n(It is NOT necessary that the algorithm discover the
 same recursion for both sums, even if they are equal; later we'll lea
rn about noncommutative LCM's and GCD's and the Euclidean algorithm fo
r dealing with that.)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "re
ad EKHAD;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%8Version~of~Feb~25,~1999
G" }}{PARA 11 "" 1 "" {TEXT -1 18 "(verbiage deleted)" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "F1 := (n,k)->binomial(n,k)^3;\nzeil
pap(F1(n,k),k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#F1G:6$%\"nG%\"
kG6\"6$%)operatorG%&arrowGF)*$-%)binomialG6$9$9%\"\"$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%\"k
G\"\"$" }}{PARA 6 "" 1 "" {TEXT -1 131 "\nand let   SUM(n)   be the su
m of   F(n,k)    with\nrespect to   k   .\n\nSUM(n)    satisfies the f
ollowing linear recurrence equation" }}{PARA 12 "" 1 "" {XPPMATH 256 "
6#,(*&,&%\"nG\"\"\"F'F'\"\"#-%$SUMG6#F&F'!\")*&,(*$F&F(!\"(F&!#@!#;F'F
'-F*6#F%F'F'*&,&F&F'F(F'F(-F*6#F6F'F'" }}{PARA 258 "" 1 "" {XPPMATH 
257 "6#%$=0.G" }}{PARA 6 "" 1 "" {TEXT -1 43 "\nPROOF: We cleverly con
struct   G(n,k)   :=" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*,%\"kG\"\"$,F
!#s\"\"\"F$\"#y%\"nG!$s#*$F*F%!$!H*$F*\"\"#!$-%*$F*\"\"%!$-\"*$F*\"\"&
!#9*&F*F%F$F(\"$Z\"*&F*F2F$F(\"#F*&F*F/F$F/!#m*&F*F%F$F/!#=*&F*F/F$F%F
2*&F*F(F$F%\"\")*$F$F%F2*&F*F/F$F(\"$\"H*$F$F/!#I*&F*F(F$F(\"$\\#*&F*F
(F$F/!#yF(,(F*!\"\"FLF(F$F(!\"$,(F*FL!\"#F(F$F(FM-%)binomialG6$F*F$F%
" }}{PARA 6 "" 1 "" {TEXT -1 20 "with the motive that" }}{PARA 12 "" 
1 "" {XPPMATH 20 "6#,(*&,&%\"nG\"\"\"F'F'\"\"#-%\"FG6$F&%\"kGF'!\")*&,
(*$F&F(!\"(F&!#@!#;F'F'-F*6$F%F,F'F'*&,&F&F'F(F'F(-F*6$F7F,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 "" {MPLTEXT 1 0 71 "F2 := (n,k) -> binomial(n,k)^2 * bi
nomial(2*k,n);\nzeilpap(F2(n,k),k,n);" }}{PARA 11 "" 1 "" {XPPMATH 20 
"6#>%#F2G:6$%\"nG%\"kG6\"6$%)operatorG%&arrowGF)*&-%)binomialG6$9$9%\"
\"#-F/6$,$F2F3F1\"\"\"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%\"kG\"\"#-F%6$,$F(F)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 l
inear recurrence equation" }}{PARA 256 "" 1 "" {XPPMATH 20 "6#,(*&,&%
\"nG\"\"\"F'F'\"\"#-%$SUMG6#F&F'!\")*&,(*$F&F(!\"(F&!#@!#;F'F'-F*6#F%F
'F'*&,&F&F'F(F'F(-F*6#F6F'F'" }}{PARA 257 "" 1 "" {XPPMATH 20 "6#%$=0.
G" }}{PARA 6 "" 1 "" {TEXT -1 43 "\nPROOF: We cleverly construct   G(n
,k)   :=" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*4,&%\"nG\"\"\"F&F&F&%\"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-F0F&F'F&F0-%)binomialG6$F%F'F(-F36$,$F'F(F%F&" }}{PARA 6 "" 
1 "" {TEXT -1 20 "with the motive that" }}{PARA 12 "" 1 "" {XPPMATH 
20 "6#,(*&,&%\"nG\"\"\"F'F'\"\"#-%\"FG6$F&%\"kGF'!\")*&,(*$F&F(!\"(F&!
#@!#;F'F'-F*6$F%F,F'F'*&,&F&F'F(F'F(-F*6$F7F,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 421 "Notice both sums satisfy the same recursion of order 2! \+
 The top order term has a leading zero coefficient if n=-2, which is n
ot a nonnegative integer, so it's not of concern.  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 60 "f1 := n -> expand(sum(F1(n,k),k=0..n));\n'f1(nn)'$'nn
'=0..10;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#f1G:6#%\"nG6\"6$%)opera
torG%&arrowGF(-%'expandG6#-%$sumG6$-%#F1G6$9$%\"kG/F6;\"\"!F5F(F(" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"\"\"\"#\"#5\"#c\"$Y$\"%_A\"&%=:\"'
g\\5\"'i\"R(\"(K4G&\")g_;Q" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 20 "And
 the same for f2:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "f2 := n -> exp
and(sum(F2(n,k),k=0..n));\n'f2(nn)'$'nn'=0..10;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%#f2G:6#%\"nG6\"6$%)operatorG%&arrowGF(-%'expandG6#-%$
sumG6$-%#F2G6$9$%\"kG/F6;\"\"!F5F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "
6-\"\"\"\"\"#\"#5\"#c\"$Y$\"%_A\"&%=:\"'g\\5\"'i\"R(\"(K4G&\")g_;Q" }}
}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "And we can have them compared dir
ectly, 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 0 0" 
13 }{VIEWOPTS 1 1 0 1 1 1803 }