{VERSION 3 0 "SGI MIPS UNIX" "3.0" } {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 Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 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 }{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 "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 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "with(MS):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 277 "Consider the Lucas numbers as defined by Lehmer, \\cite\{Lehmer\}. To avoid confusion with the Lucas numbers \+ defined in Graham, Knuth and Patashnik, \\cite\{Knuth\} we will call t hese Lucas numbers, ``Lucas numbers type II''. When looking at the Luc as numbers type II generated by " }{XPPEDIT 18 0 "x*exp(x)/(exp(2*x)- 1);" "6#*(%\"xG\"\"\"-%\$expG6#F\$F%,&-F'6#*&\"\"#F%F\$F%F%\"\"\"!\"\"F/ " }{TEXT -1 0 "" }{TEXT -1 55 ", \\Label\{defn:Lucas II\} the calculat ion of interest is " }{XPPEDIT 18 0 "product(exp(2*x*omega[m]^i)-1,i = 0 .. m-1);" "6#-%(productG6\$,&-%\$expG6#*(\"\"#\"\"\"%\"xGF,)&%&omegaG 6#%\"mG%\"iGF,F,\"\"\"!\"\"/F3;\"\"!,&F2F,\"\"\"F5" }{TEXT -1 0 "" } {TEXT -1 8 ", where " }{XPPEDIT 18 0 "omega[m];" "6#&%&omegaG6#%\"mG" }{TEXT -1 4 " is " }{XPPEDIT 18 0 "exp(2*Pi*I/m);" "6#-%\$expG6#**\"\"# \"\"\"%#PiGF(%\"IGF(%\"mG!\"\"" }{TEXT -1 7 ". Set " }{XPPEDIT 18 0 " t(x) = exp(2*x)-1;" "6#/-%\"tG6#%\"xG,&-%\$expG6#*&\"\"#\"\"\"F'F.F.\" \"\"!\"\"" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "s(x) = x*exp(x);" "6#/- %\"sG6#%\"xG*&F'\"\"\"-%\$expG6#F'F)" }{TEXT -1 3 ". " }{TEXT -1 100 " Assume that the function is being multisectioned by 4. Notice deg^d(t( x)) = 0, and hence that deg^d(" }{XPPEDIT 18 0 "product(t(x*omega[m]^i ),i = 0 .. m-1);" "6#-%(productG6\$-%\"tG6#*&%\"xG\"\"\")&%&omegaG6#%\" mG%\"iGF+/F1;\"\"!,&F0F+\"\"\"!\"\"" }{TEXT -1 26 ") = 0. Notice that deg^P(" }{XPPEDIT 18 0 "t(x);" "6#-%\"tG6#%\"xG" }{TEXT -1 19 ") = 2, hence deg^P(" }{XPPEDIT 18 0 "t(x)*t(-x);" "6#*&-%\"tG6#%\"xG\"\"\"-F %6#,\$F'!\"\"F(" }{TEXT -1 152 ") is at most 4. So for the first step \+ only a linear recurrence relation to degree 8 is needed. So first cal culate the taylor series approximation for " }{XPPEDIT 18 0 "t(x);" "6 #-%\"tG6#%\"xG" }{TEXT -1 12 ", call this " }{XPPEDIT 18 0 "8!*T(x);" "6#*&-%*factorialG6#\"\")\"\"\"-%\"TG6#%\"xGF(" }{TEXT -1 11 " (scale \+ by " }{XPPEDIT 18 0 "8!;" "6#-%*factorialG6#\"\")" }{TEXT -1 45 " to a void having to work over the rationals)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "t := exp(2*x)-1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %\"tG,&-%\$expG6#,\$%\"xG\"\"#\"\"\"!\"\"F," }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 41 "T := convert(taylor(t,x=0,9),polynom)*8!;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"TG,2%\"xG\"&S1)*\$)F&\"\"#\"\"\"F'*\$)F&\" \"\$F+\"&gP&*\$)F&\"\"%F+\"&!)o#*\$)F&\"\"&F+\"&_2\"*\$)F&\"\"'F+\"%%e\$*\$) F&\"\"(F+\"%C5*\$)F&\"\")F+\"\$c#" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Now multiply " }{XPPEDIT 18 0 "T(x);" "6#-%\"TG6#%\"xG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "T(-x);" "6#-%\"TG6#,\$%\"xG!\"\"" }{TEXT -1 18 " and divide by 8!." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 42 "T 2 := convert(series(expand(T * subs(x=-x," }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "T)),x,9),polynom)/8!;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T2G,**\$)%\"xG\"\"#\"\"\"!'!Gh\"*\$)F(\"\"%F*!&gP&*\$)F(\"\"'F*! %or*\$)F(\"\")F*!\$7&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 43 "Determine \+ the intersting (non-zero) values." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "for i from 0 to 4 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 39 " b[i] := coeff(T2,x,2*i)*(2*i)!/8!; " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"!F '" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"\"!\")" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"#!#K" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"\$!\$G\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6# \"\"%!\$7&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "Solve this linear re currence relation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "rec : = `recurrence/solve/linalg`(b, f, x, 2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\$recG/-%\"fG6#%\"xG,\$-F'6#,&F)\"\"\"!\"#F.\"\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "t2 := rec, f, x, [f(0) = b[0], f(1) = 0, " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "f(2) = b[1], f(3) = 0, f( 4) = b[2], f(5) = 0, " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "f(6) = b[3 ], f(7) = 0, f(8) = b[4]];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#t2G6& /-%\"fG6#%\"xG,\$-F(6#,&F*\"\"\"!\"#F/\"\"%F(F*7+/-F(6#\"\"!F6/-F(6#F/F 6/-F(6#\"\"#!\")/-F(6#\"\"\$F6/-F(6#F1!#K/-F(6#\"\"&F6/-F(6#\"\"'!\$G\"/ -F(6#\"\"(F6/-F(6#\"\")!\$7&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 97 "No w determine what deg^P(T2(x)) and deg^d(T2(x)) are, as these will be u seful in the calculation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "`egf/metric/P`(t2);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\$" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 19 "`egf/metric/d`(t2);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 166 "Notice that deg^P(t2(x)) = 3, and hence deg^P(t2(x)* t2( I*x)) is at most 9. Thus only the first 18 terms of the polynomial ap proximation needs to be calculated, say " }{XPPEDIT 18 0 "18!*t2(x);" "6#*&-%*factorialG6#\"#=\"\"\"-%#t2G6#%\"xGF(" }{TEXT -1 11 " (scale b y " }{XPPEDIT 18 0 "18!;" "6#-%*factorialG6#\"#=" }{TEXT -1 63 " to av oid having to work over the rationals). Call this T2(x)." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "Fun := `egf/makeproc`(t2):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "T2 := add (Fun(i)*x^i/i!,i=0 ..18)*18!;" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#>%#T2G,4*\$)%\"xG\"\"#\" \"\"!2+?\"H#[\\4c#*\$)F(\"\"%F*!1+SIu#)\\O&)*\$)F(\"\"'F*!1+s!*p(*>Q6*\$) F(\"\")F*!/+[c\$)**H\")*\$)F(\"#5F*!.!)GgKLh\$*\$)F(\"#7F*!-gt#\\\\4\"*\$)F (\"#9F*!+?>[1C*\$)F(\"#;F*!)K!3,%*\$)F(\"#=F*!')GC&" }}}{EXCHG {PARA 0 " " 0 "" {TEXT -1 16 "So now multiply " }{XPPEDIT 18 0 "T2(x);" "6#-%#T2 G6#%\"xG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "T2(I*x);" "6#-%#T2G6#*&% \"IG\"\"\"%\"xGF(" }{TEXT -1 18 " and divide by 18!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "T3 := convert(series(expand(T2 * subs(x=I *x, T2)),x,19),polynom)/18!;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#T3G ,**\$)%\"xG\"\"%\"\"\"!3+![;HzzV-\"*\$)F(\"\")F*\"1+W\")R&*RwA*\$)F(\"#7F *!/?:TILX9*\$)F(\"#;F*\",c-)[P?" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 41 "Collect the interesting (non-zero) terms." }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 21 "for i from 0 to 4 do " }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 40 " b[i] := coeff(T3,x,4*i)*(4*i)!/18!; " }}{PARA 0 " > " 0 "" {MPLTEXT 1 0 3 "od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"b G6#\"\"!F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"\"!\$%Q" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"#\"&OV\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"\$!(W83\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>&%\"bG6#\"\"%\")wXem" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 38 "Solve this linear recurrence relation." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "rec := `recurrence/solve/linalg`(b, f, x, 4);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\$recG/-%\"fG6#%\"xG,&-F'6#,&F)\"\" \"!\")F.\"%C5-F'6#,&F)F.!\"%F.!#[" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 77 "This also could have been done by using the Maple function for thi s technique" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "`bottom/ms/l inalg/fft2`(t,f,x,4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&/-%\"fG6#%\"x G,&-F%6#,&F'\"\"\"!\")F,\"%C5-F%6#,&F'F,!\"%F,!#[F%F'7+/-F%6#\"\"!F8/- F%6#F,F8/-F%6#\"\"#F8/-F%6#\"\"\$F8/-F%6#\"\"%!\$%Q/-F%6#\"\"&F8/-F%6#\" \"'F8/-F%6#\"\"(F8/-F%6#\"\")\"&OV\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 25 "Which is the \+ same result." }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{MARK "14 0 0" 15 } {VIEWOPTS 1 1 0 1 1 1803 }