{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 9 ", where " }{XPPEDIT 18 0 "b[i]; " "6#&%\"bG6#%\"iG" }{TEXT -1 40 " satisfy the linear recurrence relat ion " }{XPPEDIT 18 0 "b[i] = b[i-1]/2+b[i-2]/4;" "6#/&%\"bG6#%\"iG,&*& &F%6#,&F'\"\"\"\"\"\"!\"\"F-\"\"#F/F-*&&F%6#,&F'F-\"\"#F/F-\"\"%F/F-" }{TEXT -1 29 ", with initial conditions of " }{XPPEDIT 18 0 "b[0] = 0, b[1] = 1/3;" "6\$/&%\"bG6#\"\"!F'/&F%6#\"\"\"*&\"\"\"\"\"\"\"\"\$!\"\"" }{TEXT -1 30 ". Notice that the compution " }{XPPEDIT 18 0 "bp[i] = \+ 2^i*b[i];" "6#/&%#bpG6#%\"iG*&)\"\"#F'\"\"\"&%\"bG6#F'F+" }{TEXT -1 39 " using the linear recurrence relation " }{XPPEDIT 18 0 "2^i*b[i] \+ = 2^(i-1)*b[i-1]+2^(i-2)*b[i-2];" "6#/*&)\"\"#%\"iG\"\"\"&%\"bG6#F'F(, &*&)\"\"#,&F'F(\"\"\"!\"\"F(&F*6#,&F'F(\"\"\"F2F(F(*&)\"\"#,&F'F(\"\"# F2F(&F*6#,&F'F(\"\"#F2F(F(" }{TEXT -1 18 ", or equivalently " } {XPPEDIT 18 0 "bp[i] = bp[i-1]+bp[i-2];" "6#/&%#bpG6#%\"iG,&&F%6#,&F' \"\"\"\"\"\"!\"\"F,&F%6#,&F'F,\"\"#F.F," }{TEXT -1 66 " gives the same result. Remember that now the initial values are " }{XPPEDIT 18 0 "b p[0] = 0;" "6#/&%#bpG6#\"\"!F'" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "bp [1] = 2/3;" "6#/&%#bpG6#\"\"\"*&\"\"#\"\"\"\"\"\$!\"\"" }{TEXT -1 31 ". Now notice that if instead " }{XPPEDIT 18 0 "bpp[i] = 3*bp[i];" "6# /&%\$bppG6#%\"iG*&\"\"\$\"\"\"&%#bpG6#F'F*" }{TEXT -1 122 " is computed \+ then the computation is wholly within the integers, as are the initial values. So from this it follows that " }{XPPEDIT 18 0 "b[i] = bpp[i] /(2^i*3);" "6#/&%\"bG6#%\"iG*&&%\$bppG6#F'\"\"\"*&)\"\"#F'F,\"\"\$F,!\" \"" }{TEXT -1 55 ". Check this by computing the first few terms of bo th " }{XPPEDIT 18 0 "bpp[i]/(2^i*3);" "6#*&&%\$bppG6#%\"iG\"\"\"*&)\"\" #F'F(\"\"\$F(!\"\"" }{TEXT -1 5 " and " }{XPPEDIT 18 0 "b[i];" "6#&%\"b G6#%\"iG" }{TEXT -1 1 "." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 60 "Bpp := `egf/makeproc`(bpp(i) = bpp(i-1) + bpp(i-2), bpp, i, " }} {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 " [bpp(0)= 0, bpp(1) = 2]):" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "seq(1/3*(1/2)^i*Bpp(i),i=0.. 10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"!#\"\"\"\"\"\$#F%\"\"'F'#F% \"\")#\"\"&\"#[#F%\"#7#\"#8\"\$#>#\"\"(\"\$G\"#\"#<\"\$%Q#\"#b\"%O:" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 78 "B := `egf/makeproc`(b(i) = b (i-1)/2 + b(i-2)/4, b, i, [b(0) = 0, b(1) = 1/3]):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "seq(B(i),i=0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"!#\"\"\"\"\"\$#F%\"\"'F'#F%\"\")#\"\"&\"#[#F%\"#7#\" #8\"\$#>#\"\"(\"\$G\"#\"#<\"\$%Q#\"#b\"%O:" }}}}{MARK "1 0 2" 8 } {VIEWOPTS 1 1 0 1 1 1803 }