{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 }} {SECT 0 {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "with(MS):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 45 "Consider the exponential generating funct ion " }{XPPEDIT 18 0 "s(x) = sum(b[i]*x^i/i!,i = 0 .. infinity);" "6#/ -%\"sG6#%\"xG-%$sumG6$*(&%\"bG6#%\"iG\"\"\")F'F/F0-%*factorialG6#F/!\" \"/F/;\"\"!%)infinityG" }{TEXT -1 15 " with a linear " }{TEXT -1 20 "r ecurrence relation " }{XPPEDIT 18 0 "b[i] = b[i-1]-b[i-2]+b[i-3];" "6# /&%\"bG6#%\"iG,(&F%6#,&F'\"\"\"\"\"\"!\"\"F,&F%6#,&F'F,\"\"#F.F.&F%6#, &F'F,\"\"$F.F," }{TEXT -1 25 ", with initial values of " }{XPPEDIT 18 0 "b[0] = 1,b[1] = 1;" "6$/&%\"bG6#\"\"!\"\"\"/&F%6#\"\"\"\"\"\"" } {TEXT -1 5 " and " }{XPPEDIT 18 0 "b[2] = 1;" "6#/&%\"bG6#\"\"#\"\"\" " }{TEXT -1 0 "" }{TEXT -1 164 ". This example multisections this li near recurrence relation by 16 at 0, using the methods described in th is subsection. First determine the value of deg^d(s(x))" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "s := b(x) = b(x-1) - b(x-2) + b(x-3 ), b, x, [b(0) = 1, b(1) = 1, b(2) = 1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"sG6&/-%\"bG6#%\"xG,(-F(6#,&F*\"\"\"!\"\"F/F/-F(6#,&F*F/!\"#F /F0-F(6#,&F*F/!\"$F/F/F(F*7%/-F(6#\"\"!F//-F(6#F/F//-F(6#\"\"#F/" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "egf/metric/d(s);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"!" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 94 "From this it follows that the multisectioned recurrence polynomial can have no multiple roots." }}{PARA 0 "" 0 "" {TEXT -1 43 "So now de termine the recurrence polynomial." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "P := convert_poly(s);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"PG,**$)%\"xG\"\"$\"\"\"\"\"\"*$)F(\"\"#F*!\"\"F(F+F/F+" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Now multiply " }{XPPEDIT 18 0 "P(x );" "6#-%\"PG6#%\"xG" }{TEXT -1 4 " by " }{XPPEDIT 18 0 "P(-x);" "6#-% \"PG6#,$%\"xG!\"\"" }{TEXT -1 12 " and expand." }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 29 "P2 := expand(subs(x=-x,P)*P);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#P2G,**$)%\"xG\"\"'\"\"\"!\"\"*$)F(\"\"%F*F+*$)F (\"\"#F*\"\"\"F2F2" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 85 "Now this po lynomial should have no multiple roots, so get rid of the multiple ro ots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "P2p := quo(P2,gcd(P 2, diff(P2,x)),x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$P2pG,&*$)%\"x G\"\"%\"\"\"!\"\"\"\"\"F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 13 "Now \+ multiply " }{XPPEDIT 18 0 "P2p(x);" "6#-%$P2pG6#%\"xG" }{TEXT -1 4 " b y " }{XPPEDIT 18 0 "P2p(x*I);" "6#-%$P2pG6#*&%\"xG\"\"\"%\"IGF(" } {TEXT -1 63 ", and expand. This gives a recurrence polynomial that di vides " }{XPPEDIT 18 0 "P(x)*P(-x)*P(I*x)*P(-I*x);" "6#**-%\"PG6#%\"xG \"\"\"-F%6#,$F'!\"\"F(-F%6#*&%\"IGF(F'F(F(-F%6#,$*&F0F(F'F(F,F(" } {TEXT -1 27 " and has no multiple roots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "P4 := expand(subs(x=x*I,P2p)*P2p);" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#P4G,(*$)%\"xG\"\")\"\"\"\"\"\"*$)F(\"\"%F*!\"#F+F+ " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Again, get rid of the multipl e roots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "P4p := quo(P4, \+ gcd(P4, diff(P4,x)),x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$P4pG,&*$ )%\"xG\"\"%\"\"\"\"\"\"!\"\"F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 17 "Lastly, multiply " }{XPPEDIT 18 0 "P4p(x);" "6#-%$P4pG6#%\"xG" } {TEXT -1 4 " by " }{XPPEDIT 18 0 "P4p(x*sqrt(I));" "6#-%$P4pG6#*&%\"xG \"\"\"-%%sqrtG6#%\"IGF(" }{TEXT -1 62 " and expand. This gives a recu rrence polynomial that divides " }{XPPEDIT 18 0 "P(x)*P(-x)*P(I*x)*P(- I*x)*P(sqrt(I)*x)*P(-sqrt(I)*x)*P(I*sqrt(I)*x)*P(-I*sqrt(I)*x);" "6#*2 -%\"PG6#%\"xG\"\"\"-F%6#,$F'!\"\"F(-F%6#*&%\"IGF(F'F(F(-F%6#,$*&F0F(F' F(F,F(-F%6#*&-%%sqrtG6#F0F(F'F(F(-F%6#,$*&-F96#F0F(F'F(F,F(-F%6#*(F0F( -F96#F0F(F'F(F(-F%6#,$*(F0F(-F96#F0F(F'F(F,F(" }{TEXT -1 27 " and has \+ no multiple roots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "P8 := expand(subs(x=x*sqrt(I),P4p)*P4p);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6 #>%#P8G,&*$)%\"xG\"\")\"\"\"!\"\"\"\"\"F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 37 "Again, get rid of the multiple roots." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 38 "P8p := quo(P8, gcd(P8, diff(P8,x)),x);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%$P8pG,&*$)%\"xG\"\")\"\"\"!\"\"\"\" \"F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 57 "So converting back gives \+ a linear recurrence relation of:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 21 "convert_rec(P8p,b,x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/-%\"bG6#%\"xG-F%6#,&F'\"\"\"!\")F+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 128 "This is the same linear recurrence relation that is deri ved using the naive technique discussed in example \\ref\{ex:Chap 2 Ex 1\}." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "egf/ms/naive(s,8 ,0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&/-%\"bG6#%\"xG-F%6#,&F'\"\"\"! \")F+F%F'7*/-F%6#\"\"!F+/-F%6#F+F1/-F%6#\"\"#F1/-F%6#\"\"$F1/-F%6#\"\" %F1/-F%6#\"\"&F1/-F%6#\"\"'F1/-F%6#\"\"(F1" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 58 "This has been automated as the Maple command egf/ms/rec ." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "egf/ms/rec(s,8,0);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6&/-%\"bG6#%\"xG-F%6#,&F'\"\"\"!\")F+F %F'7*/-F%6#\"\"!F+/-F%6#F+F1/-F%6#\"\"#F1/-F%6#\"\"\$F1/-F%6#\"\"%F1/-F %6#\"\"&F1/-F%6#\"\"'F1/-F%6#\"\"(F1" }}}}{MARK "1 0 10" 156 } {VIEWOPTS 1 1 0 1 1 1803 }