{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 " 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+\"# " 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,!#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 }