{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 52 "Consider the example of the Fibonacci num
bers.  Let " }{XPPEDIT 18 0 "s(x) = sum(b[i]*x^i/i!,i = 0 .. infinity)
;" "6#/-%\"sG6#%\"xG-%$sumG6$*(&%\"bG6#%\"iG\"\"\")F'F/F0-%*factorialG
6#F/!\"\"/F/;\"\"!%)infinityG" }{TEXT -1 8 ", where " }{XPPEDIT 18 0 "
b[0] = 0;" "6#/&%\"bG6#\"\"!F'" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "b[
1] = 1;" "6#/&%\"bG6#\"\"\"\"\"\"" }{TEXT -1 146 ".  Consider multisec
tioning this by 17 at 0.  From Lemma \\ref\{lem:d pow P\} the size of \+
the new linear recurrence relation will be at most 17 times" }{TEXT 
-1 45 " deg^P(s(x)) = 2.  Further deg^d(s(x)) = 0 so" }{TEXT -1 234 " \+
 it follows that the values $b_1$, $b_2$, ... $b_\{17 \\times 2 \\time
s 2\}$ are needed.  All but $b_\{17\}$, $b_\{34\}$, $b_\{51\}$, and $b
_\{68\}$ will be zero, so only these four values are needed to determi
ne the linear recurrence relation.\n" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 56 "s := b(i) = b(i-1) + b(i-2), b, i, [b(0) = 0, b(1) = \+
1];" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>-%\"sG6#%\"xG6&/-%\"bG6#%\"iG,
&-F+6#,&F-\"\"\"!\"\"F2F2-F+6#,&F-F2!\"#F2F2F+F-7$/-F+6#\"\"!F</-F+6#F
2F2" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "`egf/metric/P`(s);" 
}}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 18 "`egf/metric/d`(s);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6
#\"\"!" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "Fib := `egf/makep
roc`(s):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 49 "So this gives the fol
lowing two linear equations:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 
0 51 "eqn1 := a[1] * Fib(17) + a[2] * Fib(34) =  Fib(51);" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#>%%eqn1G/,&&%\"aG6#\"\"\"\"%(f\"&F(6#\"\"#\"(()
Gq&\",u5,l.#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 51 "eqn2 := a[1
] * Fib(34) + a[2] * Fib(51) =  Fib(68);" }}{PARA 11 "" 1 "" {XPPMATH 
20 "6#>%%eqn2G/,&&%\"aG6#\"\"\"\"(()Gq&&F(6#\"\"#\",u5,l.#\"/T\"[-YBF(
" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 35 "Solving these two equations g
ives  " }{XPPEDIT 18 0 "a[1];" "6#&%\"aG6#\"\"\"" }{TEXT -1 5 " and " 
}{XPPEDIT 18 0 "a[2];" "6#&%\"aG6#\"\"#" }{TEXT -1 1 "." }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "solve(\{eqn1, eqn2\});" }}{PARA 11 
"" 1 "" {XPPMATH 20 "6#<$/&%\"aG6#\"\"\"F(/&F&6#\"\"#\"%rN" }}}{EXCHG 
{PARA 0 "" 0 "" {TEXT -1 46 "So this gives the linear recurrence relat
ion  " }{XPPEDIT 18 0 "b[i] = 3571*b[i-17]+b[i-28];" "6#/&%\"bG6#%\"iG
,&*&\"%rN\"\"\"&F%6#,&F'F+\"#<!\"\"F+F+&F%6#,&F'F+\"#GF0F+" }{TEXT -1 
102 ".  This could have also been solved by using the linear algebra p
ackage in Maple in the following way." }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 54 "C := matrix(2,2,[Fib(17), Fib(34), Fib(34), Fib(51)])
;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"CG-%'matrixG6#7$7$\"%(f\"\"((
)Gq&7$F+\",u5,l.#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "B := v
ector(2, [Fib(51), Fib(68)]);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"B
G-%'vectorG6#7$\",u5,l.#\"/T\"[-YBF(" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 14 "linsolve(C,B);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'
vectorG6#7$\"\"\"\"%rN" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 67 "There i
s also a command in Maple to do this called `egf/ms/linalg`." }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "`egf/ms/linalg`(s,17,0);" }}
{PARA 12 "" 1 "" {XPPMATH 20 "6&/-%\"bG6#%\"iG,&-F%6#,&F'\"\"\"!#MF,F,
-F%6#,&F'F,!#<F,\"%rNF%F'7D/-F%6#\"\"!F7/-F%6#F,F,/-F%6#\"\"#F7/-F%6#
\"\"$F7/-F%6#\"\"%F7/-F%6#\"\"&F7/-F%6#\"\"'F7/-F%6#\"\"(F7/-F%6#\"\")
F7/-F%6#\"\"*F7/-F%6#\"#5F7/-F%6#\"#6F7/-F%6#\"#7F7/-F%6#\"#8F7/-F%6#
\"#9F7/-F%6#\"#:F7/-F%6#\"#;F7/-F%6#\"#<F7/-F%6#\"#=\"%%e#/-F%6#\"#>F7
/-F%6#\"#?F7/-F%6#\"#@F7/-F%6#\"#AF7/-F%6#\"#BF7/-F%6#\"#CF7/-F%6#\"#D
F7/-F%6#\"#EF7/-F%6#\"#FF7/-F%6#\"#GF7/-F%6#\"#HF7/-F%6#\"#IF7/-F%6#\"
#JF7/-F%6#\"#KF7/-F%6#\"#LF7" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 36 "S
o this again gives the same result." }{MPLTEXT 1 0 0 "" }}}}{MARK "1 0
 7" 30 }{VIEWOPTS 1 1 0 1 1 1803 }