{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 "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 "" 3 258 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 45 "/home/m262f99/KOEPF/works
heetsV.4/hw2ansm.mws" }{MPLTEXT 1 0 0 "" }}{PARA 258 "" 0 "" {TEXT 
257 45 "Math 262a, Fall 1999, Glenn Tesler\nHomework 2" }{MPLTEXT 1 0 
0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 64 "Problem 4a solved the \"hu
manoid way\", but with maple assistance:" }}{PARA 0 "> " 0 "" 
{MPLTEXT 1 0 34 "Fnk := (n,k) -> binomial(n,k)*x^k;" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#>%$FnkG:6$%\"nG%\"kG6\"6$%)operatorG%&arrowGF)*&-%)bi
nomialG6$9$9%\"\"\")%\"xGF2F3F)F)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
55 "Form the desired recurrence, with unknown coefficients:" }}{PARA 
0 "> " 0 "" {MPLTEXT 1 0 65 "rec := a*Fnk(n,k) + b*Fnk(n+1,k) + c*Fnk(
n,k+1) + d*Fnk(n+1,k+1);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%$recG,**
(%\"aG\"\"\")%\"xG%\"kGF(-%)binomialG6$%\"nGF+F(F(*(%\"bGF(F)F(-F-6$,&
F/F(F(F(F+F(F(*(%\"cGF()F*,&F+F(F(F(F(-F-6$F/F8F(F(*(%\"dGF(F7F(-F-6$F
4F8F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Divide through by the \+
unshifted function:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "rec/Fnk(n,k)
;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*(,**(%\"aG\"\"\")%\"xG%\"kGF'-%)
binomialG6$%\"nGF*F'F'*(%\"bGF'F(F'-F,6$,&F.F'F'F'F*F'F'*(%\"cGF')F),&
F*F'F'F'F'-F,6$F.F7F'F'*(%\"dGF'F6F'-F,6$F3F7F'F'F'F(!\"\"F+F>" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 55 "Reduce all the ratios to rational \+
functions of n and k:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "simplify(
\");" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#*(,F*(%\"aG\"\"\"%\"nGF'%\"kGF
'F'*&F&F'F(F'F'F&F'*&F&F'F)\"\"#!\"\"*(%\"bGF'F(F'F)F'F'*&F/F'F(F'F'*&
F/F'F)F'F'F/F'**%\"cGF'%\"xGF'F)F'F(F'!\"#*(F3F'F4F'F)F'F-*(F3F'F4F'F)
F,F'*(F3F'F4F'F(F,F'*(F3F'F4F'F(F'F'*(%\"dGF'F4F'F(F,F'*(F;F'F4F'F(F'F
,**F;F'F4F'F(F'F)F'F-*&F;F'F4F'F'*(F;F'F4F'F)F'F-F',(F(F'F'F'F)F-F-,&F
)F'F'F'F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "Clear denominators (
or take the numerator):" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "numer(\")
;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,F*(%\"aG\"\"\"%\"nGF&%\"kGF&F&*&
F%F&F'F&F&F%F&*&F%F&F(\"\"#!\"\"*(%\"bGF&F'F&F(F&F&*&F.F&F'F&F&*&F.F&F
(F&F&F.F&**%\"cGF&%\"xGF&F(F&F'F&!\"#*(F2F&F3F&F(F&F,*(F2F&F3F&F(F+F&*
(F2F&F3F&F'F+F&*(F2F&F3F&F'F&F&*(%\"dGF&F3F&F'F+F&*(F:F&F3F&F'F&F+**F:
F&F3F&F'F&F(F&F,*&F:F&F3F&F&*(F:F&F3F&F(F&F," }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 137 "This is a polynomial in k.  We want it to be true for \+
all integer values of k, so it must be the 0 polynomial. Collect it in
 powers of k." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 13 "collect(\",k);" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#,8*&,&%\"aG!\"\"*&%\"cG\"\"\"%\"xGF*F*
F*%\"kG\"\"#F**&,0*&%\"bGF*%\"nGF*F*F(F'F1F**(F)F*F+F*F2F*!\"#*&F&F*F2
F*F**(%\"dGF*F+F*F2F*F'*&F7F*F+F*F'F*F,F*F**(F7F*F+F*F2F-F*F5F*F&F*F8F
*F3F*F0F*F6F-F1F**(F)F*F+F*F2F-F*" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 
45 "Separate the coefficients of the powers of k." }}{PARA 0 "> " 0 "
" {MPLTEXT 1 0 12 "coeffs(\",k);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6%,4
*(%\"dG\"\"\"%\"xGF&%\"nG\"\"#F&*&%\"aGF&F(F&F&F+F&*&F%F&F'F&F&*(%\"cG
F&F'F&F(F&F&*&%\"bGF&F(F&F&*(F%F&F'F&F(F&F)F0F&*(F.F&F'F&F(F)F&,&F+!\"
\"*&F.F&F'F&F&,0F/F&F5F4F0F&F-!\"#F*F&F1F4F,F4" }}}{EXCHG {PARA 0 "" 
0 "" {TEXT -1 150 "This gives a system of equations for the unknowns a
,b,c,d.  They'll potentially depend on n, but there are no k's in the \+
system, so they'll be k-free." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "so
ls := solve(\{\"\},\{a,b,c,d\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%
%solsG<&/%\"cG,$%\"dG!\"\"/%\"aG,$*&F)\"\"\"%\"xGF/F*/%\"bG\"\"!/F)F)
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "subs(sols,rec);" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6#,(**%\"dG\"\"\"%\"xGF&)F'%\"kGF&-%)bin
omialG6$%\"nGF)F&!\"\"*(F%F&)F',&F)F&F&F&F&-F+6$F-F1F&F.*(F%F&F0F&-F+6
$,&F-F&F&F&F1F&F&" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "recF:=
subs(sols,a*F(n,k)+b*F(n+1,k)+c*F(n,k+1)+d*F(n+1,k+1));" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#>%%recFG,(*(%\"dG\"\"\"%\"xGF(-%\"FG6$%\"nG%\"kG
F(!\"\"*&F'F(-F+6$F-,&F.F(F(F(F(F/*&F'F(-F+6$,&F-F(F(F(F3F(F(" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "recF := subs(d=1,recF);" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%recFG,(*&%\"xG\"\"\"-%\"FG6$%\"nG%
\"kGF(!\"\"-F*6$F,,&F-F(F(F(F.-F*6$,&F,F(F(F(F1F(" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 55 "Let f(n)=sum(F(n,k),k=-infinity..infinity).  This \+
gives" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "recf := subs(''F(n+i,k+j)=
f(n+i)'$i=0..1'$j=0..1,recF);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%re
cfG,(*&%\"xG\"\"\"-%\"fG6#%\"nGF(!\"\"F)F--F*6#,&F,F(F(F(F(" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "rsolve(recf=0,f(n));" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%\"fG6#\"\"!\"\"\"),&%\"xGF(F(F(%\"
nGF(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 89 "Now get the initial value
 f(0).  Maple won't do the sum correctly for -infinity..infinity" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "sum(Fnk(0,k),k=-infinity..infinity)
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%$sumG6$*&)%\"xG%\"kG\"\"\"-%)bi
nomialG6$\"\"!F)F*/F);,$%)infinityG!\"\"F2" }}}{EXCHG {PARA 0 "" 0 "" 
{TEXT -1 66 "But if we recognize F(n,k)=0 for k<0, we can get it to do
 the sum." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "sum(Fnk(0,k),k=0..infi
nity);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 40 "Problem 4a solved with Koepf'
s software:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "read `hsum.mpl`;" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#%ZCopyright~1998~~Wolfram~Koepf,~Konra
d-Zuse-Zentrum~BerlinG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "r
ec := fasenmyer(binomial(n,k)*x^k,k,f(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 45 "rec := fas
enmyer(binomial(n,k)*x^k,k,f(n),1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#>%$recG/,&-%\"fG6#,&%\"nG\"\"\"F,F,F,*&-F(6#F+F,,&%\"xGF,F,F,F,!\"\"
\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rsolve(rec,f(n));
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*&-%\"fG6#\"\"!\"\"\"),&%\"xGF(F(F
(%\"nGF(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "rsolve(\{rec,f(
0)=1\},f(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#),&%\"xG\"\"\"F&F&%\"
nG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 17 "Koepf
 # 4.1 (2.2)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "fasenmyer((-1)^k*bi
nomial(n,k),k,f(n),0);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error, (in kfre
erec) no kfree recurrence equation of order (, 0, 0, ) exists" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "fasenmyer((-1)^k*binomial(n,
k),k,f(n),1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%\"fG6#,&%\"nG\"\"
\"F)F)\"\"!" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 5 "(2.3)" }}{PARA 0 ">
 " 0 "" {MPLTEXT 1 0 36 "fasenmyer(binomial(n,k)^2,k,f(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 36 "fasenmyer(binomial(n,k)^2,k,f(n),1);" }}{PARA 8 "" 1 
"" {TEXT -1 76 "Error, (in kfreerec) no kfree recurrence equation of o
rder (, 1, 1, ) exists" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "f
asenmyer(binomial(n,k)^2,k,f(n),2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#/,&*&,&%\"nG\"\"\"\"\"#F(F(-%\"fG6#F&F(F(*&-F+6#,&F'F(F(F(F(,&F'F)\"
\"$F(F(!\"#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rsolve(
\",f(n));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*,)\"\"%%\"nG\"\"\"-%&GAM
MAG6#,&F&F'#F'\"\"#F'F'-F)6#,&F&F'F'F'!\"\"%#PiG#F1F--%\"fG6#\"\"!F'" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "
" {TEXT -1 5 "(2.4)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "fasenmyer((-
1)^k*binomial(n,k)^2,k,f(n),1);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error,
 (in kfreerec) no kfree recurrence equation of order (, 1, 1, ) exists
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 43 "fasenmyer((-1)^k*binomi
al(n,k)^2,k,f(n),2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*&,&%\"nG\"
\"\"\"\"#F(F(-%\"fG6#F&F(F(*&-F+6#F'F(,&F'F(F(F(F(\"\"%\"\"!" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rsolve(\",f(n));" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#-%'rsolveG6$/,&*&,&%\"nG\"\"\"\"\"#F+F+-%\"f
G6#F)F+F+*&-F.6#F*F+,&F*F+F+F+F+\"\"%\"\"!F1" }}}{EXCHG {PARA 0 "" 0 "
" {TEXT -1 42 "It's not going to do it for us too easily." }}{PARA 0 "
> " 0 "" {MPLTEXT 1 0 10 "rec := \"\";" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%$recG/,&*&,&%\"nG\"\"\"\"\"#F*F*-%\"fG6#F(F*F**&-F-6#F)F*,&F)F
*F*F*F*\"\"%\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 7 "Even n:" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "subs(n=2*m,rec); subs(f = proc(k) g
(k/2) end,\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*&,&%\"mG\"\"#F(
\"\"\"F)-%\"fG6#F&F)F)*&-F+6#,$F'F(F),&F'F(F)F)F)\"\"%\"\"!" }}{PARA 
12 "" 1 "" {XPPMATH 20 "6#/,&*&,&%\"mG\"\"#F(\"\"\"F)-:6#%\"kG6\"F.F.-
%\"gG6#,$9$#F)F(F.F.6#F&F)F)*&-F+6#,$F'F(F),&F'F(F)F)F)\"\"%\"\"!" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "eval(\");" }}{PARA 11 "" 1 "
" {XPPMATH 20 "6#/,&*&,&%\"mG\"\"#F(\"\"\"F)-%\"gG6#,&F'F)F)F)F)F)*&-F
+6#F'F),&F'F(F)F)F)\"\"%\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 15 "rsolve(\",g(m));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*.)!\"\"%\"m
G\"\"\")\"\"%F&F'-%&GAMMAG6#,&F&F'#F'\"\"#F'F'-F+6#,&F&F'F'F'F%%#PiG#F
%F/-%\"gG6#\"\"!F'" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "Use the ini
tial condition g(0)=f(2*0)=f(0)=1." }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 6 "Odd n:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 58 "subs(n=2*m+1,rec); \+
eval(subs(f=proc(k) g((k-1)/2) end,\"));" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#/,&*&,&%\"mG\"\"#\"\"$\"\"\"F*-%\"fG6#F&F*F**&-F,6#,&F'F(F*F*F*,
&F'F(F(F*F*\"\"%\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*&,&%\"mG
\"\"#\"\"$\"\"\"F*-%\"gG6#,&F'F*F*F*F*F**&-F,6#F'F*,&F'F(F(F*F*\"\"%\"
\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "rsolve(\",g(m));" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#,$*.-%&GAMMAG6#,&%\"mG\"\"\"F*F*F*-F&6
#,&F)F*#\"\"$\"\"#F*!\"\"%#PiG#F*F0-%\"gG6#\"\"!F*)F1F)F*)\"\"%F)F*F3
" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "
" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 11 "Koepf # 4.5" }{MPLTEXT 1 0 0 
"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "kfreerec(binomial(n-k,
k),k,n,0,0,F,a);" }}{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 38 "kfreerec(binomial(n-k,k),k,n,1,1,F,
a);" }}{PARA 8 "" 1 "" {TEXT -1 76 "Error, (in kfreerec) no kfree recu
rrence equation of order (, 1, 1, ) exists" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 38 "kfreerec(binomial(n-k,k),k,n,2,2,F,a);" }}{PARA 12 
"" 1 "" {XPPMATH 20 "6#/,.*&&%\"aG6$\"\"!F)\"\"\"-%\"FG6$%\"nG%\"kGF*F
**&&F'6$\"\"#F3F*-F,6$F.,&F/F*F*F*F*!\"\"*&F&F*-F,6$,&F.F*F*F*F6F*F**&
F&F*-F,6$,&F.F*F3F*F6F*F7*&F1F*-F,6$F;,&F/F*F3F*F*F7*&F1F*-F,6$F?FCF*F
*F)" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "nkrec:=\":" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 81 "nkrec1 := subs(a[0,0]=1,a[2,
2]=0,nkrec);\nnkrec2 := subs(a[2,2]=0,a[0,0]=1,nkrec);" }}{PARA 11 "" 
1 "" {XPPMATH 20 "6#>%'nkrec1G/,(-%\"FG6$%\"nG%\"kG\"\"\"-F(6$,&F*F,F,
F,,&F+F,F,F,F,-F(6$,&F*F,\"\"#F,F0!\"\"\"\"!" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%'nkrec2G/,(-%\"FG6$%\"nG%\"kG\"\"\"-F(6$,&F*F,F,F,,&F
+F,F,F,F,-F(6$,&F*F,\"\"#F,F0!\"\"\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 57 "nrec:=subs('('F(n+i,k+j)=s(n+i)'$j=0..2)'$i=0..2,nkre
c1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%nrecG/,(-%\"sG6#%\"nG\"\"\"
-F(6#,&F*F+F+F+F+-F(6#,&F*F+\"\"#F+!\"\"\"\"!" }}}{EXCHG {PARA 0 "" 0 
"" {TEXT -1 45 "Or, we could do all of that with one command:" }}
{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "fasenmyer(binomial(n-k,k),k,s(n),2)
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,(-%\"sG6#%\"nG!\"\"-F&6#,&F(\"
\"\"F-F-F)-F&6#,&F(F-\"\"#F-F-\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
-1 188 "What we just did is not quite legal.  We want k=0..floor(n/2),
 but we just used the theory for k=-infinity..infinity.  However, the \+
function does not vanish ouside the range 0..floor(n/2):" }{MPLTEXT 1 
0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "Fnk := (n,k)->bino
mial(n-k,k);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FnkG:6$%\"nG%\"kG6
\"6$%)operatorG%&arrowGF)-%)binomialG6$,&9$\"\"\"9%!\"\"F3F)F)" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "'F(2,k)=Fnk(2,k)'$k=-5..5;" 
}}{PARA 12 "" 1 "" {XPPMATH 20 "6-/-%\"FG6$\"\"#!\"&\"\"!/-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=/-F%6$F'F'F)/-F%6$F'\"\"$F9/-F%6$F'\"\"%\"\"&/-F%6$F'FL!#@" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 579 "It does vanish for k=floor(n/2)+1
,...,n, so let s(n)=sum(binomial(n-k,k),k=0..n).\nThen sum up nkrec1 f
or k=0..n.  The three terms give:\n          sum(F(n,k),k=0..n) = s(n)
\n          sum(F(n+1,k+1),k=0..n) = f(n+1) - F(n+1,0) + F(n+1,n+1) = \+
s(n+1)-1+0 = s(n+1)-1\n          sum(F(n+2,k+1),k=0..n) = f(n+2) - F(n
+2,0) + F(n+2,n+1) = s(n+2)-1  for n>0\n            (for n=0 we have F
(n+2,n+1)=F(2,1)=binomial(2-1,1)=1 so it's false)\n          Combining
 the three gives s(n)+s(n+1)-s(n+2) = 0.\nSo the correct recursion was
 derived by invalid reasoning.\nNext we need initial conditions." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "
" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 44 "sumfn
 := n -> sum(Fnk(n,k),k=0..floor(n/2));" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%&sumfnG:6#%\"nG6\"6$%)operatorG%&arrowGF(-%$sumG6$-%$FnkG6$9$%
\"kG/F3;\"\"!-%&floorG6#,$F2#\"\"\"\"\"#F(F(" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 19 "'sumfn(n)'$n=0..10;" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6-\"\"\"F#\"\"#\"\"$\"\"&\"\")\"#8\"#@\"#M\"#b\"#*)" }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 147 "Since it's the same 2nd order rec
urrence as the Fibonacci numbers and the first two numbers agree, the \+
sum does in fact give the Fibonacci numbers." }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" {TEXT -1 15 "Koepf # \+
4.15(a)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "Fnk := (n,k)->(-1)^k * b
inomial(n,k);\nfasenmyer(Fnk(n,k),k,f(n),1);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%$FnkG:6$%\"nG%\"kG6\"6$%)operatorG%&arrowGF)*&)!\"\"9
%\"\"\"-%)binomialG6$9$F0F1F)F)" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%
\"fG6#,&%\"nG\"\"\"F)F)\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 225 "
That's wrong because the sum is supposed to be over k=0..m, but this i
s k=-infinity..infinity.\nThe bound m is not natural, so additional (u
nwanted) terms are included.\nInstead, get the k-free recurrence, and \+
sum it manually. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "nkrec := kfree
rec(Fnk(n,k),k,n,1,1,F,a);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&nkrec
G/,(*&&%\"aG6$\"\"\"F+F+-%\"FG6$%\"nG%\"kGF+F+*&F(F+-F-6$F/,&F0F+F+F+F
+!\"\"*&F(F+-F-6$,&F/F+F+F+F4F+F+\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 30 "nkrec := subs(a[1,1]=1,nkrec);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%&nkrecG/,(-%\"FG6$%\"nG%\"kG\"\"\"-F(6$F*,&F+F,F,F,!
\"\"-F(6$,&F*F,F,F,F/F,\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 84 "L
et f(n)=sum(F(n,k),k=0..m).  Compute the sum of nkrec for k=0..m as we
 did in #4.5:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 82 "nrec := f(
n) - (f(n)-Fnk(n,0)+Fnk(n,m+1)) + (f(n+1)-Fnk(n+1,0)+Fnk(n+1,m+1)) = 0
; " }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%%nrecG/,(*&)!\"\",&%\"mG\"\"\"
F,F,F,-%)binomialG6$%\"nGF*F,F)-%\"fG6#,&F0F,F,F,F,*&F(F,-F.6$F4F*F,F,
\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "solve(nrec,\{f(n+1
)\});" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"fG6#,&%\"nG\"\"\"F*F*,
&*&)!\"\",&%\"mGF*F*F*F*-%)binomialG6$F)F/F*F**&F-F*-F26$F(F/F*F." }}}
{EXCHG {PARA 0 "" 0 "" {TEXT -1 113 "We see Pascal's triangle there.  \+
Can we get maple to see it too?  Yes, but not automatically with this \+
software.." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "simplify(\");" }}
{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"fG6#,&%\"nG\"\"\"F*F*,&*&)!\"\"
%\"mGF*-%)binomialG6$F),&F/F*F*F*F*F.*&F-F*-F16$F(F3F*F*" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "rec := \";" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#>%$recG<#/-%\"fG6#,&%\"nG\"\"\"F,F,,&*&)!\"\"%\"mGF,-%)
binomialG6$F+,&F1F,F,F,F,F0*&F/F,-F36$F*F5F,F," }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 19 "convert(rec,GAMMA);" }}{PARA 11 "" 1 "" 
{XPPMATH 20 "6#<#/-%\"fG6#,&%\"nG\"\"\"F*F*,&**)!\"\"%\"mGF*-%&GAMMAGF
'F*-F16#,&F/F*\"\"#F*F.-F16#,&F)F*F/F.F.F.**F-F*-F16#,&F)F*F5F*F*F2F.-
F16#,(F)F*F*F*F/F.F.F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "s
implify(\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"fG6#,&%\"nG\"\"
\"F*F***)!\"\"%\"mGF*-%&GAMMAG6#,&F.F*F*F*F--F06#,(F)F*F*F*F.F-F--F0F'
F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "convert(\",binomial);
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"fG6#,&%\"nG\"\"\"F*F**&)!\"
\"%\"mGF*-%)binomialG6$F)F.F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 14 "subs(n=n-1,\");" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#/-%\"fG6#%
\"nG*&)!\"\"%\"mG\"\"\"-%)binomialG6$,&F(F-F+F-F,F-" }}}{EXCHG {PARA 
3 "" 0 "" {TEXT -1 15 "Koepf # 4.15(c)" }}{PARA 0 "> " 0 "" {MPLTEXT 
1 0 58 "Fnk := (n,k)->binomial(k,n);\nfasenmyer(Fnk(n,k),k,f(n),1);" }
}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FnkG:6$%\"nG%\"kG6\"6$%)operatorG%
&arrowGF)-%)binomialG6$9%9$F)F)" }}{PARA 8 "" 1 "" {TEXT -1 77 "Error,
 (in fasenmyer) wrong number (or type) of parameters in function norma
l" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> \+
" 0 "" {MPLTEXT 1 0 31 "kfreerec(Fnk(n,k),k,n,1,1,F,a);" }}{PARA 11 "
" 1 "" {XPPMATH 20 "6#/,(*&&%\"aG6$\"\"!F)\"\"\"-%\"FG6$%\"nG%\"kGF*F*
*&F&F*-F,6$,&F.F*F*F*F/F*F**&F&F*-F,6$F3,&F/F*F*F*F*!\"\"F)" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "nkrec := subs(a[0,0]=1,\");
" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&nkrecG/,(-%\"FG6$%\"nG%\"kG\"\"
\"-F(6$,&F*F,F,F,F+F,-F(6$F/,&F+F,F,F,!\"\"\"\"!" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 170 "Let f(n) = sum(binomial(k,n),k=0..m) = sum(Fnk(n,
k),k=0..m).\nThe bounds are not natural, so they can't be extended to \+
-infinity..+infinity.\nSumming nkrec for k=0..m gives" }}{PARA 0 "> " 
0 "" {MPLTEXT 1 0 61 "nrec := f(n) + f(n+1) - (f(n+1)-Fnk(n+1,0)+Fnk(n
+1,m+1)) = 0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%nrecG/,(-%\"fG6#%
\"nG\"\"\"-%)binomialG6$\"\"!,&F*F+F+F+F+-F-6$,&%\"mGF+F+F+F0!\"\"F/" 
}}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "solve(\",f(n));" }}{PARA 
11 "" 1 "" {XPPMATH 20 "6#,&-%)binomialG6$\"\"!,&%\"nG\"\"\"F*F*!\"\"-
F%6$,&%\"mGF*F*F*F(F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }
}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "
" {TEXT -1 15 "Koepf # 4.11(a)" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 59 "f
asenmyer(hyperterm([-n,1+beta],[1,1+alpha],x,k),k,f(n),3);" }}{PARA 
12 "" 1 "" {XPPMATH 20 "6#/,**&,2*&%\"nG\"\"\"%&alphaGF)\"\"#F(\"#:F*
\"\"&*&%\"xGF)F(F)!\"\"*&F/F)%%betaGF)F0F/!\"$*$F(F+\"\"$\"#>F)F)-%\"f
G6#,&F(F)F+F)F)F0*(F:F),*F(F5F/F0\"\"'F)F*F)F)-F86#,&F(F)F)F)F)F)*(F:F
)F@F)-F86#F(F)F0*(,&F(F)F5F)F),(F(F)F*F)F5F)F)-F86#FEF)F)\"\"!" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 3 "" 0 "" 
{TEXT -1 12 "Koepf # 4.18" }}{PARA 0 "" 0 "" {TEXT -1 17 "q-Chu-Vander
monde" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 67 "qfasenmyer(qphihyperterm([
q^(-n),b],[c],q,c*q^n/b,k),q,k,S(n),1,1);" }}{PARA 8 "" 1 "" {TEXT -1 
75 "Error, (in qfasenmyer) No k-free recurrence equation of order (1,1
) exists." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "qfasenmyer(qph
ihyperterm([q^(-n),b],[c],q,c/q^(-n)/b,k),q,k,S(n),1,2);" }}{PARA 12 "
" 1 "" {XPPMATH 20 "6#/,(*(%\"bG\"\"\",&*&%\"cGF')%\"qG,&%\"nGF'F'F'F'
F'!\"\"F'F'-%\"SG6#,&F.F'\"\"#F'F'F/*&,.*(F*F'F&F')F,,&F4F'F.F4F'F/F)F
'*&F&F'F,F'F/F&F/*(F*F'F&F'F+F'F'*&F&F')F,F3F'F'F'-F16#F-F'F'**F,F',&F
&F'*&F*F')F,F.F'F/F',&F/F'F+F'F'-F16#F.F'F/\"\"!" }}}{EXCHG {PARA 0 "
" 0 "" {TEXT -1 19 "q-Pfaff-Saalschuetz" }}{PARA 0 "> " 0 "" {MPLTEXT 
1 0 160 "qfasenmyer(qpochhammer(q^(-n),q,k)*qpochhammer(a,q,k)*qpochha
mmer(b,q,k)/qpochhammer(q,q,k)/qpochhammer(c,q,k)/qpochhammer(a*b/c/q^
(n-1),q,k)*q^k,q,k,S(n),1,1);" }}{PARA 8 "" 1 "" {TEXT -1 77 "Error, (
in qkfreerec) no kfree recurrence equation of order (, 1, 1, ) exists
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "for higher orders the computa
tions timings are very poor and were interrupted" }}}{EXCHG {PARA 0 ">
 " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 41 }{VIEWOPTS 1 1 0 1 1 
1803 }