{VERSION 4 0 "IBM INTEL NT" "4.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {CSTYLE "" -1 256 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }{PSTYLE "Normal " -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 {CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 4 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 8 2 1 0 1 0 2 2 0 1 }{PSTYLE "Warning" -1 7 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 2 2 2 2 2 1 1 1 3 1 } 1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE " " -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Plot" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Norma l" -1 256 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {PARA 4 "" 0 "" {TEXT -1 30 "Module 7: Discrete Mathematics" } }{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 3 "" 0 "" {TEXT -1 15 "702 : Re cursion" }}{PARA 0 "" 0 "" {TEXT -1 14 " Gregory Moore" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 256 "" 0 "" {TEXT -1 13 "P U R P O S E" }} {PARA 0 "" 0 "" {TEXT -1 114 "In this module, we'll examine recursion \+ in various forms and from symbolic, numeric, and geometric points of v iew." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "_ ______________________________________________________________________ ________________" }}{PARA 4 "" 0 "" {TEXT -1 33 "A. Explicit & Recursi ve Sequences" }}{PARA 0 "" 0 "" {TEXT -1 87 "_________________________ ______________________________________________________________" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 132 "For a sequence to be defined explicitly, there must be a function or rule that allows the computation of any member \+ of the sequence." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "s := k -> 3*k +2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"sGR6#%\"kG6\"6$%)operatorG%&arrowGF(,&9$ \"\"$\"\"#\"\"\"F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "s eq( s(k), k = 1..12);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6.\"\"&\"\")\"# 6\"#9\"#<\"#?\"#B\"#E\"#H\"#K\"#N\"#Q" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 386 "The \+ basic idea of a recursively defined sequence is that the defiition of \+ each term depends on one or more previous terms. There are two basic c omponents. First, you need a starting value which acts as a seed for t he rest of the sequence. Next, you need a rule which tells you how to \+ compute one term, given the previous one. Together these two component s form the recursive definition." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "s||1 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s1G\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 48 "for k from 2 to 10 do s||k := 3*s||(k-1) +2; od;" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#s2G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#> %#s3G\"#<" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s4G\"#`" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#>%#s5G\"$h\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# >%#s6G\"$&[" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s7G\"%d9" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s8G\"%tV" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#s9G\"&@J\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$s10G\"&l$R" }}} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 442 "In a sense, the explicitly defined sequence al lows for random access to any element in the sequence with direct comp utatioin, while a recursive definition requires the computation of all of the elements prior to the desired element in a sequential manner. \+ Clearly an explicit definition is more convenient in this way. However , many sequences are much more easily defined by recursive definitions . Here is an example of the Fibonacci numbers." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "FF||0 := 0; FF||1 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF0G\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF1G \"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "for k from 2 to 1 0 do FF||k := FF||(k-1) + FF||(k-2); od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF2G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF3G\"\"#" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF4G\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF5G\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF6G \"\")" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF7G\"#8" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF8G\"#@" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$FF 9G\"#M" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%FF10G\"#b" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 154 "There is an explicit formula for this sequence, which we will see later in this module, however, it is a not an extremely simp le not easily found formula." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "_______________ ______________________________________________________________________ __" }}{PARA 4 "" 0 "" {TEXT -1 34 "B. Resolving 1st Order Recurrences " }}{PARA 0 "" 0 "" {TEXT -1 87 "_____________________________________ __________________________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 247 "One of our goals is to take recursively defined sequences, or \+ recurrences, and find explicit definitions for the same sequence. We w ill start with \"1st order recurrences\" which are recurrences which o nly depend on a single previous term at a time." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 275 "Maple has a specific command, rsolve, to solve recurrences. Le ts see how it works. Here is the recursive definition of a sequence, f ollowed by the rslove command. The final command, seq, is a way of the n evaluting this function to find the first 20 elements of the sequen ce." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "\{ f(n) = f(n-1) + 9, f(0) = 7\};" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# <$/-%\"fG6#%\"nG,&-F&6#,&F(\"\"\"F-!\"\"F-\"\"*F-/-F&6#\"\"!\"\"(" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "rsolve( %, f(k));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&\"\"(\"\"\"*&\"\"*F%%\"kGF%F%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "seq( subs( k = j, %), j = 0..20);" }}{PARA 11 "" 1 "" {XPPMATH 20 "67\"\"(\"#;\"#D\"#M\"#V\"#_\"#h\"#q\"# z\"#))\"#(*\"$1\"\"$:\"\"$C\"\"$L\"\"$U\"\"$^\"\"$g\"\"$p\"\"$y\"\"$(= " }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 62 "This can also be done in slightly more co mpact way as follows." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 46 "rsolve( \+ \{f(n) = 3 * f(n-1), f(0) =1 \}, f(k));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#)\"\"$%\"kG" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "seq(su bs(k = j, %) , j = 0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6-\"\"\"\" \"$\"\"*\"#F\"#\")\"$V#\"$H(\"%(=#\"%hl\"&$o>\"&\\!f" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "_________________________ ______________________________________________________________" }} {PARA 4 "" 0 "" {TEXT -1 23 "C. 2nd Order Recurrence" }}{PARA 0 "" 0 " " {TEXT -1 87 "_______________________________________________________ ________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 286 "A 2nd re currence is a recurively defined sequence which depends on two previou s terms to find each additional term. Many of these sequences have mor e complicated formulas. The method is essentially the same. One differ ence is that there needs to be two seed values to start the process." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "restart;" }}}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 56 "rsolve( \{ f(n) = f(n-1) + 2*f(n-2), f(0..1) = 1\}, f(k));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&)!\"\"%\"kG#\"\"\" \"\"$*&#\"\"#F)F()F,F&F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "seq( subs( k =j, %), j = 0..10);" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6-\"\"\"F#\"\"$\"\"&\"#6\"#@\"#V\"#&)\"$r\"\"$T$\"$$o" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "____________________ ___________________________________________________________________" } }{PARA 4 "" 0 "" {TEXT -1 23 "D. Recursive Procedures" }}{PARA 0 "" 0 "" {TEXT -1 87 "______________________________________________________ _________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 344 "Another \+ aspect to recursion is its application to computer programming and Map le programming. As in most computer languages ( such as Pascal , C++, \+ and Fortran ) its possible to define procedures or functions. Maple al lows for this same capability. In particular, we can use this method t o define recursive procedures and examine how they work." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 439 "Here is an example of a recursive procedure to compute the factorial of a number. For example, 5 factorial is 5! = 5 4 3 \+ 2 1 = 120. Of course, Maple already has this command built in, but w e,re going to use it as an example of defining our own procedures. The procedure should be entered in its entirety at one command prompt. Yo u can enter multiple lines without executing by hitting RETURN ( Macit osh ) or SHIFT - RETURN (Windows )." }}{PARA 0 "" 0 "" {TEXT -1 1 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 61 "fact := proc(n)\nif n = 0 \+ then 1;\nelse n*fact(n-1); ; fi;\nend:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 417 "The name of the procedure is fact. \+ It receives a value of n and if that value is 0 , it returns the valu e of 1. Otherwise, it returns n times the value of the procedure evalu ated at n - 1. In Maple, the if - then - else - fi is a decision comma nd that allows one of two outcomes depending on the condition - in thi s case the whether or not n = 0 is a true statement. Lets see what hap pens when we use this procedure." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "fact(5);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$?\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "fact(1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "fac t(10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(+)GO" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 316 "As you can see, this procedure apparently computes the factori al of what ever number we give it. Here is another version of the proc edure. This version makes the same computation, but also prints out th e intermediate values and the current value of n. This provides a wind ow to what is going on inside the procedure." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 221 "fact := proc(n) local x;\n print( cat(\"n=\" ,n));\n if n = 0 then print(\"- - - bottom of the heap - - -\"); 1;\n else x := fact(n-1);\n print( cat(\"n=\", n, \" \+ fact(\",n,\")=\", x)); n*x;\nfi; end:" }}{PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "fact(5); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=56\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=46\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=36\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=26\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=06\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?-~-~-~bottom~of~the~heap~-~-~-6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=1~~~~fact(1)=16\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#Q1n=2~~~~fact(2)=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=3~~~~fact(3)=26\"" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#Q1n=4~~~~fact(4)=66\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q2n=5~~~~fa ct(5)=246\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"$?\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "fact(1);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=06\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?-~-~-~bottom~of~the~heap~-~-~-6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=1~~~~fact(1)=16\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "fact(10);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q%n=106\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=96\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6# Q$n=86\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=76\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=66\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=56\" " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=46\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=36\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=26\"" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q$n=06\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q?-~-~-~bot tom~of~the~heap~-~-~-6\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=1~~~~f act(1)=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=2~~~~fact(2)=16\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q1n=3~~~~fact(3)=26\"" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#Q1n=4~~~~fact(4)=66\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q2n=5~~~~fact(5)=246\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q3n=6~~~~fact(6)=1206\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q3n=7~~~ ~fact(7)=7206\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q4n=8~~~~fact(8)=50 406\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#Q5n=9~~~~fact(9)=403206\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#Q8n=10~~~~fact(10)=3628806\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"(+)GO" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 146 "The proc edure works its way down to the bottom where n = 0, then works it way \+ back up gradually forming the product that will be the final result." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 97 "Here is an example of a procedure to create the Fibonacci sequence which show s its inner working." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 149 "fib := pr oc(n)\nprint(n);\nif (( n = 1) or ( n = 2))\nthen print(` - - - bottom of the heap - - - n = ` ,n); 1;\nelse fib(n - 1) + fib(n - 2); fi; \+ end:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "fib(4);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$ " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~ bottom~of~the~heap~-~-~-~~~n~=~G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "fib(6);" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~ =~G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~ =~G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 " " {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"\"" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~bottom~of~the~heap~-~-~-~~~n~=~G\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%G~-~-~-~ bottom~of~the~heap~-~-~-~~~n~=~G\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\")" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "__________________________________ _____________________________________________________" }}{PARA 4 "" 0 "" {TEXT -1 39 "E. Recursive Expressions & Fixed Points" }}{PARA 0 "" 0 "" {TEXT -1 87 "____________________________________________________ ___________________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 92 "Related to this concept, there are also \+ expressions which are recursively defined such as " }{XPPEDIT 18 0 " sqrt(1+sqrt(1+sqrt(1+sqrt(1+x))));" "6#-%%sqrtG6#,&\"\"\"F'-F$6#,&F'F' -F$6#,&F'F'-F$6#,&F'F'%\"xGF'F'F'F'" }{TEXT -1 69 " This can be thoug ht of as a recursively defined sequence such as " }{XPPEDIT 18 0 "sq rt(1),sqrt(1+sqrt(1)),sqrt(1+sqrt(1+sqrt(1)));" "6%-%%sqrtG6#\"\"\"-F$ 6#,&F&F&-F$6#F&F&-F$6#,&F&F&-F$6#,&F&F&-F$6#F&F&F&" }{TEXT -1 54 ",... . . We can express this as a recurrence f(n) = " }{XPPEDIT 18 0 "sq rt(1+f(n-1));" "6#-%%sqrtG6#,&\"\"\"F'-%\"fG6#,&%\"nGF'F'!\"\"F'" } {TEXT -1 304 " where f( 1 ) = 0 :. Unfortunately, the rsolve command c an not resolve this kind of recurrence. However, we can deal with this in another way. We can simply define a function based on this recurre nce, then iterate the function - that is repeatedly compose the f unction with itself and evaluate at 1." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "f := x -> sqrt( 1 + x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% \"fGR6#%\"xG6\"6$%)operatorG%&arrowGF(-%%sqrtG6#,&\"\"\"F09$F0F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "f(f(0));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$-%%sqrtG6#\"\"#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 11 "f(f(f(0)));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#*$-% %sqrtG6#,&\"\"\"F(*$-F%6#\"\"#F(F(F(" }}}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 88 "We can iterate the function 10 times \+ by repeatedly composing it with itself in this way." }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "(f@@10)(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#* $-%%sqrtG6#,&\"\"\"F(*$-F%6#,&F(F(*$-F%6#,&F(F(*$-F%6#,&F(F(*$-F%6#,&F (F(*$-F%6#,&F(F(*$-F%6#,&F(F(*$-F%6#,&F(F(*$-F%6#,&F(F(*$-F%6#,&F(F(% \"xGF(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(F(" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 62 "In fact, we can see what \+ is happening by doing this in a loop." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "for k from 1 to 12 do (f @@k)(0) = evalf( (f@@k)(0)); od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/ \"\"\"$F$\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#\"\"#\" \"\"$\"+iN@99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\" \"\"F)*$-F&6#\"\"#F)F)F)$\"+uRx`:!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F)F)$\"+#=`!) f\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F &6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F)F)F)F)$\"+ax%=h\"!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$ -F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F)F)F)F)F)F)$\"+177;;!\"*" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)* $-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F)F)F)F)F)F)F) F)$\"+)zUuh\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\" \"\"F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F )*$-F&6#\"\"#F)F)F)F)F)F)F)F)F)F)F)F)F)$\"+!H^yh\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$-F&6#,&F)F)* $-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F )F)F)F)F)F)F)F)F)F)F)F)$\"+Jv(zh\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$ -F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F) F)F)F)F)F)F)F)F)F)F)F)F)F)$\"+Ul,=;!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$ -F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6# \"\"#F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)$\"+(fG!=;!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#,&\"\"\"F)*$-F&6#,&F)F)*$-F&6#,&F) F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#,&F)F)*$- F&6#,&F)F)*$-F&6#,&F)F)*$-F&6#\"\"#F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F)F )F)F)F)$\"+BB.=;!\"*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "for k from 1 to 12 do evalf( (f@@k)(0) ); od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"\"\"\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+iN@ 99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+uRx`:!\"*" }}{PARA 11 " " 1 "" {XPPMATH 20 "6#$\"+#=`!)f\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+ax%=h\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+177;;!\"* " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+)zUuh\"!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#$\"+!H^yh\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$ \"+Jv(zh\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+Ul,=;!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+(fG!=;!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#$\"+BB.=;!\"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 264 "It appears that the values are convergin g to a number around 1.618033989. But how can we find the exact value \+ o the expression? Suppose for a moment that the values of f( n ) where identical. Lets say x = f(n) = f(n+1) = ...... Then the recursion wou ld become x = " }{XPPEDIT 18 0 "sqrt(1+x);" "6#-%%sqrtG6#,&\"\"\"F'%\" xGF'" }{TEXT -1 99 " , or more generally, f(x) = x. If we simply so lve that equation for x, we will have our answer." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "f(x) = x;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%% sqrtG6#,&\"\"\"F)%\"xGF)F)F*" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "solve( %,x); evalf(%);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#,&#\" \"\"\"\"#F%*&F$F%-%%sqrtG6#\"\"&F%F%" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#$\"+*)R.=;!\"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 40 "A value for which f(x) = x, is called a " }{TEXT 256 11 " fixed point" }{TEXT -1 1 "." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "____________________ ___________________________________________________________________" } }{PARA 4 "" 0 "" {TEXT -1 18 "F. Newton's Method" }}{PARA 0 "" 0 "" {TEXT -1 87 "_________________________________________________________ ______________________________" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 284 "An example of a recursive formula is New ton's Method for finding roots of a function. This method requires tha t you be familiar with a little bit of Calculus. Newton's Method is to start with a guess for what a root may be. The initial guess is x0 , \+ then repeatedly apply this formula" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 232 "to get better and better guesses. In man y cases, the formula will converge to the value of a root fairly quick ly. Lets start with a function f(x), and then define the function N(x) to give the next guess according to Newton's method" }}{PARA 0 "" 0 " " {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "f := x -> \+ x^2 -2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fGR6#%\"xG6\"6$%)operat orG%&arrowGF(,&*$)9$\"\"#\"\"\"F1F0!\"\"F(F(F(" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 28 "N := x -> x - f(x)/ D(f)(x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"NGR6#%\"xG6\"6$%)operatorG%&arrowGF(,&9$\"\"\"*& -%\"fG6#F-F.--%\"DG6#F1F2!\"\"F7F(F(F(" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 44 "Like any recursive definition, we start with" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "x||0 := 1;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "for k from 1 to 10 do x||k := evalf( N(x||(k-1))) od ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x1G$\"+++++:!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x2G$\"+nmm;9!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x3G$\"+'o:UT\"!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%#x4G$\"+iN@99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x5G$\"+iN@ 99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x6G$\"+iN@99!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x7G$\"+iN@99!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#x8G$\"+iN@99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%#x9G$\"+iN@99!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x10G$\"+iN @99!\"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 71 "The values seem to converge quite \+ quickly. The actual solution is this." }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "sqrt(2) : % = evalf(%); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/*$-%%sqrtG6#\"\"#\"\"\"$\"+iN@99! \"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 87 "_______ ______________________________________________________________________ __________" }}{PARA 4 "" 0 "" {TEXT -1 42 "G. Geometric View of Recurs ive Convergence" }}{PARA 0 "" 0 "" {TEXT -1 87 "______________________ _________________________________________________________________" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 204 "The subj ect of fixed points of recursions is an interesting one for many reaso ns and one we can investigate algebraically, numerically, and geometri cally. We will need the following special plot function." }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "resta rt; with(plots):" }}{PARA 7 "" 1 "" {TEXT -1 50 "Warning, the name ch angecoords has been redefined\n" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 502 "rec_plot := proc( f1, a , b, x0)\nlocal x1, x2, y1, y2, i , p 1, p2, p3, n, a1,a2;\nx2 := x0; y2:= 0; n :=10;\nfor i from 1 to n do\nx1 := x2; y1 := y2; y2:=f(x1); x2 := y2;\np1[i] := plot( [[ x1, y1], [x1, y2]], x = a..b, color =red):\np2[i] := plot( [[x1, y2], \+ [x2, y2]], x = a..b , color = yellow):\nod:\ndisplay( plot( f1(x), x = a..b, thickness = 3, color = blue), \n plot(x, x = a.. b, thickness = 1, color = black),\n seq( p1[i], i = 1..n) , seq( p2[i], i = 1..n) ); end:" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 28 "Here is a recursive formula." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "f := x -> (x+6)/2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"fGR6#%\"xG6\"6$%)operatorG%&arrowGF(,&9$#\"\"\"\"\" #\"\"$F/F(F(F(" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "x||0 := 2 ;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x0G\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 55 "for k from 1 to 16 do x||k := evalf( f(x||(k- 1) )); od;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x1G$\"\"%\"\"!" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x2G$\"+++++]!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#x3G$\"+++++b!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%#x4G$\"++++]d!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x5G$\"++++ ve!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x6G$\"+++]Pf!\"*" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x7G$\"+++vof!\"*" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%#x8G$\"++]P%)f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%#x9G$\"++v=#*f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x10G$\"+ ]P4'*f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x11G$\"+vo/)*f!\"*" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x12G$\"+QM-**f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x13G$\"+><^**f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x14G$\"+gev**f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#>%$x15G$\"+Iz()**f!\"*" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%$x16G$\" +l*Q***f!\"*" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 113 "It appears to converge b ut to where exactly? We can use the same method of finding the fixed p oint as used above." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "f(x) = x; solve(%, x);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#/,&%\"xG#\"\"\"\"\"#\"\"$F'F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 116 "A geometric view of t his situation will show not only the convergence but also the steps le ading to the convergence." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 " " 0 "" {TEXT -1 0 "" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "left \+ := 0; right := 7; start:=2;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%le ftG\"\"!" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&rightG\"\"(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&startG\"\"#" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 36 "rec_plot( f(x), left, right, start);" }}{PARA 13 "" 1 "" {GLPLOT2D 400 300 300 {PLOTDATA 2 "6:-%'CURVESG6%7S7$$\"\"!F)$\" \"$F)7$$\"+\"z+e_\"!#5$\"+S+HwI!\"*7$$\"+,>R`GF/$\"+&fpE9$F27$$\"+`pSY VF/$\"+[.KF2$\"+JG8^RF27$$\"+s2O[?F2$ \"+'Q!=CSF27$$\"+G\"H5=#F2$\"+kX^!4%F27$$\"+NYyQBF2$\"+=BRpTF27$$\"+VU UsCF2$\"+A@@OUF27$$\"+w)yyi#F2$\"+Q%RRJ%F27$$\"+oD[lFF2$\"+%GTFQ%F27$$ \"+EcX;HF2$\"+8yAeWF27$$\"+!o<-1$F2$\"+S)3,`%F27$$\"+,$=-@$F2$\"+]\"4^ g%F27$$\"+(plzM$F2$\"+[G)Rn%F27$$\"+s[a'\\$F2$\"+OCF[ZF27$$\"+yo(3l$F2 $\"+R%Qa#[F27$$\"+ULA&y$F2$\"+r;h#*[F27$$\"+07KIRF2$\"+-1;l\\F27$$\"+% \\@-3%F2$\"+Z26S]F27$$\"+$opoA%F2$\"+U[V8^F27$$\"+Y$f(oVF2$\"+t'zV=&F2 7$$\"+DOIEXF2$\"+7=:j_F27$$\"+nT'ym%F2$\"+%3KRL&F27$$\"+h-,>[F2$\"+I^] 4aF27$$\"+(3rf&\\F2$\"+Wb)zZ&F27$$\"+Yaq0^F2$\"+BF&Gb&F27$$\"+4QfY_F2$ \"+/pHBcF27$$\"+VF'QR&F2$\"+s8$pp&F27$$\"+X]%y`&F2$\"+AD#*odF27$$\"+r6 e)o&F2$\"+'e!HWeF27$$\"+vzvLeF2$\"+))*yo\"fF27$$\"+FAA#)fF2$\"+966\"*f F27$$\"+>rXHhF2$\"+g&GZ1'F27$$\"+%p]ZE'F2$\"+Z`PKhF27$$\"+)R7)>kF2$\"+ *>1*4iF27$$\"+N9]elF2$\"+=2DziF27$$\"+vGP1nF2$\"+Qk=`jF27$$\"+7Z!z%oF2 $\"+cB&RU'F27$$\"\"(F)$\"+++++lF2-%'COLOURG6&%$RGBGF(F($\"*++++\"!\")- %*THICKNESSG6#F+-F$6%7S7$F(F(7$$\"3gmmm\"z+e_\"!#=Fg[l7$$\"3sLL3->R`GF i[lF[\\l7$$\"3mmm;apSYVFi[lF^\\l7$$\"3Onm;z'=$\\eFi[lFa\\l7$$\"3!RL$3F t3XtFi[lFd\\l7$$\"3tmmTNj&=t)Fi[lFg\\l7$$\"33+](=`xn,\"!#F\\]lF ]^l7$$\"3;++]s2O[?F\\]lF`^l7$$\"3um;aG\"H5=#F\\]lFc^l7$$\"3^LL$ej%yQBF \\]lFf^l7$$\"3mLLLVUUsCF\\]lFi^l7$$\"35+](o()yyi#F\\]lF\\_l7$$\"3GLLLo D[lFF\\]lF__l7$$\"3P+](oibk\"HF\\]lFb_l7$$\"3a+]i!o<-1$F\\]lFe_l7$$\"3 qLL3-$=-@$F\\]lFh_l7$$\"3kL$3xplzM$F\\]lF[`l7$$\"3gmm\"H([a'\\$F\\]lF^ `l7$$\"3wm;ayo(3l$F\\]lFa`l7$$\"3?+]7VLA&y$F\\]lFd`l7$$\"3'pm;a?@.$RF \\]lFg`l7$$\"3)******\\\\@-3%F\\]lFj`l7$$\"3Q++v$opoA%F\\]lF]al7$$\"3c +](oMf(oVF\\]lF`al7$$\"3#)***\\ii.j_%F\\]lFcal7$$\"3%GLL$oT'ym%F\\]lFf al7$$\"3'3++DE5!>[F\\]lFial7$$\"3Mm;a)3rf&\\F\\]lF\\bl7$$\"3*4++vW0d5& F\\]lF_bl7$$\"3;L$3-\"QfY_F\\]lFbbl7$$\"3C+]PWF'QR&F\\]lFebl7$$\"3[LL$ e/Xy`&F\\]lFhbl7$$\"3m**\\(=<\"e)o&F\\]lF[cl7$$\"3%ymmm(zvLeF\\]lF^cl7 $$\"3-nm\"zAAA)fF\\]lFacl7$$\"3LM$3-7d%HhF\\]lFdcl7$$\"3#4++]p]ZE'F\\] lFgcl7$$\"3$QL$e*R7)>kF\\]lFjcl7$$\"3'pmmmV,&elF\\]lF]dl7$$\"3<+](o(GP 1nF\\]lF`dl7$$\"3g+]78Z!z%oF\\]lFcdl7$FdzFdz-Fiz6&F[[lF)F)F)-F`[l6#\" \"\"-F$6$7$7$$\"\"#F)F(7$F_el$\"\"%F)-Fiz6&F[[lF\\[lF(F(-F$6$7$7$FbelF bel7$Fbel$\"\"&F)Fdel-F$6$7$7$F[flF[fl7$F[fl$\"3++++++++bF\\]lFdel-F$6 $7$7$FbflFbfl7$Fbfl$\"3+++++++]dF\\]lFdel-F$6$7$7$FiflFifl7$Fifl$\"3++ +++++veF\\]lFdel-F$6$7$7$F`glF`gl7$F`gl$\"3++++++]PfF\\]lFdel-F$6$7$7$ FgglFggl7$Fggl$\"3++++++vofF\\]lFdel-F$6$7$7$F^hlF^hl7$F^hl$\"3+++++]P %)fF\\]lFdel-F$6$7$7$FehlFehl7$Fehl$\"3+++++v=#*fF\\]lFdel-F$6$7$7$F\\ ilF\\il7$F\\il$\"3++++]P4'*fF\\]lFdel-F$6$7$FaelFiel-Fiz6&F[[lF\\[lF\\ [lF(-F$6$7$FjelF`flFhil-F$6$7$FaflFgflFhil-F$6$7$FhflF^glFhil-F$6$7$F_ glFeglFhil-F$6$7$FfglF\\hlFhil-F$6$7$F]hlFchlFhil-F$6$7$FdhlFjhlFhil-F $6$7$F[ilFailFhil-F$6$7$Fbil7$FcilFcilFhil-%+AXESLABELSG6%Q\"x6\"Q!6\" %(DEFAULTG-%%VIEWG6$;F(FdzF]\\m" 1 2 0 1 10 0 2 9 1 4 2 1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve 4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve 11" "Cur ve 12" "Curve 13" "Curve 14" "Curve 15" "Curve 16" "Curve 17" "Curve 1 8" "Curve 19" "Curve 20" "Curve 21" "Curve 22" }}}}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 332 "The thick blue line is t he function f(x). The thin black line is the line y = x. Each of the v ertical red lines indicates a new xk. The yellow lines show how the y \+ values \"bounce\" off of the black y = x line to become new xk values . Finally the green oval indicates where the values converge within a \+ small distance of one another." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "0 0" 8 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }