{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 "" 1 12 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "terminal" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 1 24 0 0 0 0 0 0 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 }{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 "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 "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 "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 257 46 "/home/m262f99/CHYZAK/work sheetsV.4/hw8ansm.mws" }{MPLTEXT 1 0 0 "" }}{PARA 258 "" 0 "" {TEXT 258 54 "Math 262a, Fall 1999, Glenn Tesler\nHomework 8\n11/24/99" }}} {EXCHG {PARA 0 "" 0 "" {TEXT 259 10 "Problem 3." }{TEXT -1 56 " We hav e two functions defined by recurrence equations: " }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "n*f(n+1)-f(n)=0;\ng(n+2)- n*g(n)=0;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&*&%\"nG\"\"\"-%\"fG6#, &F&F'F'F'F'F'-F)6#F&!\"\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&- %\"gG6#,&%\"nG\"\"\"\"\"#F*F**&F)F*-F&6#F)F*!\"\"\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 50 "We want to find a recurrence equation sat isfied by" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "h(n) := f(n)*g(n)-g(n);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>-%\" hG6#%\"nG,&*&-%\"fGF&\"\"\"-%\"gGF&F,F,F-!\"\"" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 162 "Build a table of shifts of h(x), reduced by the rec urrence equations that f(n),g(n) satisfy.\nThe result will only involv e f(n), g(n), g(n+1), and no other shifts:" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 88 "myreduce := proc(fn)\n subs(f(n+1)=-f(n)/n, g(n+2 )=n*g(n),g(n+3)=(n+1)*g(n+1), fn)\nend:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 128 "dh[0] := h(n);\nfor k from 1 to 6 do\n dh[k] := myreduce(subs(n=n+1,dh[k-1]));\nod; k := 'k': # reset k to unevaluate d symbol " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#dhG6#\"\"!,&*&-%\"fG6 #%\"nG\"\"\"-%\"gGF,F.F.F/!\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&% #dhG6#\"\"\",&*(-%\"fG6#%\"nGF'F-!\"\"-%\"gG6#,&F-F'F'F'F'F.F/F." }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#dhG6#\"\"#,&*(-%\"fG6#%\"nG\"\"\", &F-F.F.F.!\"\"-%\"gGF,F.F.*&F-F.F1F.F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#dhG6#\"\"$,&**-%\"fG6#%\"nG\"\"\"F-!\"\",&F-F.\"\"#F.F/-%\"g G6#,&F-F.F.F.F.F/*&F5F.F2F.F/" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%#d hG6#\"\"%,&**-%\"fG6#%\"nG\"\"\",&F-F.F.F.!\"\",&F-F.\"\"$F.F0-%\"gGF, F.F.*(,&F-F.\"\"#F.F.F-F.F3F.F0" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&% #dhG6#\"\"&,&*,-%\"fG6#%\"nG\"\"\"F-!\"\",&F-F.\"\"#F.F/,&F-F.\"\"%F.F /-%\"gG6#,&F-F.F.F.F.F/*(,&F-F.\"\"$F.F.F7F.F4F.F/" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>&%#dhG6#\"\"',&*,-%\"fG6#%\"nG\"\"\",&F-F.F.F.!\"\", &F-F.\"\"$F.F0,&F-F.\"\"&F.F0-%\"gGF,F.F.**,&F-F.\"\"%F.F.,&F-F.\"\"#F .F.F-F.F5F.F0" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 74 "Symbollically, a ll of the above are in the span of the following elements:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 53 "B_module := [ f(n)*g(n), f(n)*g(n+1), g(n), g(n+1) ];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%)B_moduleG7&*&-%\"fG6# %\"nG\"\"\"-%\"gGF)F+*&F'F+-F-6#,&F*F+F+F+F+F,F/" }}}{EXCHG {PARA 0 " " 0 "" {TEXT 256 294 "(Note: it's possible that when we plug in the so lutions for f(n), g(n), that the above would be dependent, but that's \+ irrelevant. We treat these as formal, linearly independent symbols, a nd the true values of these give a space that's a \"homomorphic image \" of the symbollic space we work in.)\n" }{TEXT -1 89 "\nwhich implie s that any 5 of these are linearly dependent (5>4), so we take dh[0].. dh[4]." }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 28 "Form a dependency equat ion. " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 104 "dependency_symbollic := a [0]*` h`(n) + sum(a[k]*` h`(n+k),k=1..4);\ndependency := sum(a[k]*dh[k ],k=0..4);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%5dependency_symbollicG ,,*&&%\"aG6#\"\"!\"\"\"-%#~hG6#%\"nGF+F+*&&F(6#F+F+-F-6#,&F/F+F+F+F+F+ *&&F(6#\"\"#F+-F-6#,&F/F+F9F+F+F+*&&F(6#\"\"$F+-F-6#,&F/F+F@F+F+F+*&&F (6#\"\"%F+-F-6#,&F/F+FGF+F+F+" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%+de pendencyG,,*&&%\"aG6#\"\"!\"\"\",&*&-%\"fG6#%\"nGF+-%\"gGF0F+F+F2!\"\" F+F+*&&F(6#F+F+,&*(F.F+F1F4-F36#,&F1F+F+F+F+F4F:F4F+F+*&&F(6#\"\"#F+,& *(F.F+F " 0 "" {MPLTEXT 1 0 0 "" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 102 "The maple command collect is for \+ polynomials, not modules, so it doesn't like the form of our basis B: " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "collect(dependency,B_module);" }}{PARA 8 "" 1 "" {TEXT -1 45 "Error, (in collect) cannot collect, f(n )*g(n)" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 265 "We could replace every thing in B by symbols f(n)*g(n)->b1, f(n)*g(n+1)->b2, etc., resultin g in linear polynomials in the b's, which are the same as a module spa nned by the b's. But instead, since the basis is generated by polynom ials in f(n), g(n), g(n+1) we do:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "B_2 := [f(n),g(n),g(n+1)];\ncollect(dependency,B_2,distributed);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$B_2G7%-%\"fG6#%\"nG-%\"gGF(-F+6#, &F)\"\"\"F/F/" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#,**(,(&%\"aG6#\"\"!\" \"\"*&&F'6#\"\"#F*,&%\"nGF*F*F*!\"\"F**(&F'6#\"\"%F*F/F1,&F0F*\"\"$F*F 1F*F*-%\"gG6#F0F*-%\"fGF:F*F**(,&*&&F'6#F*F*F0F1F1*(&F'6#F7F*F0F1,&F0F *F.F*F1F1F*-F96#F/F*F;F*F**&,(F&F1*&F,F*F0F*F1*(F3F*FEF*F0F*F1F*F8F*F* *&,&F@F1*&FCF*F/F*F1F*FFF*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "B_cofs := coeffs(\",B_2);" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%' B_cofsG6&,(&%\"aG6#\"\"!\"\"\"*&&F(6#\"\"#F+,&%\"nGF+F+F+!\"\"F+*(&F(6 #\"\"%F+F0F2,&F1F+\"\"$F+F2F+,&&F(6#F+F2*&&F(6#F8F+F0F+F2,(F'F2*&F-F+F 1F+F2*(F4F+,&F1F+F/F+F+F1F+F2,&*&F:F+F1F2F2*(F=F+F1F2FBF2F2" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "B_sol := solve(\{B_cofs\},\{ 'a[k]'$k=0..4\});" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%&B_solG<'/&%\"a G6#\"\"$\"\"!/&F(6#\"\"#F-/&F(6#\"\"\"F+/&F(6#\"\"%,$*(F-F3,**$%\"nGF* F3*$F " 0 "" {MPLTEXT 1 0 49 "hDE := subs(B_sol,dependency_symbollic):\nhDE = 0;" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#/,(*,&%\"aG6#\"\"#\"\"\"%\"nGF*,(\"\" &F**$F+F)F*F+F-F*,,!\"\"F**$F+\"\"%F**$F+\"\"$\"\"'F.\"#6F+F5F0-%#~hG6 #F+F*F0*&F&F*-F86#,&F+F*F)F*F*F***F&F*,*F3F*F.F2F+F)!\"$F*F*F/F0-F86#, &F+F*F2F*F*F0\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "where a[2] \+ is anything at all. Let's clear denominators:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 54 "hDE := subs(a[2]=denom(hDE),hDE):\nmap(factor,hDE) = \+ 0;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#/,(*(%\"nG\"\"\",(\"\"&F'*$F&\" \"#F'F&F)F'-%#~hG6#F&F'!\"\"*&,,F/F'*$F&\"\"%F'*$F&\"\"$\"\"'F*\"#6F&F 6F'-F-6#,&F&F'F+F'F'F'*(,&F&F'F5F'F',(F*F'F&F'F/F'F'-F-6#,&F&F'F3F'F'F /\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 119 "Chyzak's routine to co mpute the same end result as the above, but using Grobner bases.:\nFir st reset all variable names." }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "rest art;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 63 "with(Groebner): wit h(Ore_algebra): with(Holonomy): with(Mgfun):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 89 "pol_to_sys(h(n)=f(n)*g(n)-g(n),\n \{[f(n), \+ \{n*f(n+1)-f(n)\}], [g(n), \{g(n+2)-n*g(n)\}]\});" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#<#,(*&,**$%\"nG\"\"$\"\"\"*$F(\"\"#\"\"%F(F,!\"$F*F*-% \"hG6#,&F(F*F-F*F*F**&,(F+\"\"&F(F5F'F*F*-F06#F(F*F**&,,F'!\"'*$F(F-! \"\"F(F:F+!#6F*F*F*-F06#,&F(F*F,F*F*F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "map(factor,op(\"));" }}{PARA 12 "" 1 "" {XPPMATH 20 " 6#,(*(,&%\"nG\"\"\"\"\"$F'F',(*$F&\"\"#F'F&F'!\"\"F'F'-%\"hG6#,&F&F'\" \"%F'F'F'*(F&F',(F&\"\"&F4F'F*F'F'-F.6#F&F'F'*&,,*$F&F1F'*$F&F(\"\"'F* \"#6F&F;F,F'F'-F.6#,&F&F'F+F'F'F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 81 "(The =0 is implied; this is the negative of the recurrence we had \+ the other way.)" }{MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0 0" 42 }{VIEWOPTS 1 1 0 1 1 1803 }