{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 }