{VERSION 5 0 "IBM INTEL NT" "5.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 "" -1 256 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 128 0 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 128 128 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 260 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 261 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 262 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 128 1 0 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 265 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 0 0 128 1 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 267 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 270 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 272 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 275 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 279 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 280 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 282 "" 0 1 0 128 128 1 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "T imes" 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 }} {SECT 0 {PARA 0 "" 0 "" {TEXT -1 0 "" }{TEXT 257 54 "High School Modul es > Precalculus by Gregory A. Moore\n" }}{PARA 3 "" 0 "" {TEXT -1 4 " " }{TEXT 256 22 "Mathematical Induction" }}{PARA 0 "" 0 "" {TEXT -1 75 "\nAn exploration of the method of mathematical induction to pro ve formulae.\n" }}{PARA 0 "" 0 "" {TEXT 258 153 "[Directions : Execute the Code Resource section first. Although there will be no output imm ediately, these definitions are used later in this worksheet.]" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 1 " \+ " }{TEXT 260 7 "0. Code" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "r estart; with(plots): " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" } }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 45 "StandardPlot := proc( ex pr )\n \n end proc:" }}}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 1 " " } {TEXT 261 40 "1. The Concept - Sum of Integers Formula" }}{PARA 0 "" 0 "" {TEXT -1 61 "\nHere is a formula the sum of the first n positive \+ integers.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "`1 + 2 + 3 + \+ .... + n` = n*(n+1)/2;" }}}{PARA 0 "" 0 "" {TEXT -1 120 "\nIn a sense \+ this formula is a function. Given an integer n, the sum of the first n integers is the value of this formula" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 20 "S := n -> n*(n+1)/2;" }}}{PARA 0 "" 0 "" {TEXT -1 79 "\nIt appears to work for n = 1, n = 2, in fact all n values through 1 5 at least." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "S(1); 1;" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "S(2); 1 + 2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 124 "for k from 1 to 15 do \n `wh en k = `, k,`, the sum is `,\n sum( j, j = 1..k),` and the form ula gives `, S(k); od;" }}}{PARA 0 "" 0 "" {TEXT -1 7 "\nSo it " } {TEXT 265 7 "appears" }{TEXT -1 536 " that this formula works - howeve r, how do we know it doesn't fail for some larger value of n? We can't check an infinite number of possible values. \n\nHere is a way. Since we know it works for some values of n, that is a good start. But now \+ if we can show that whenever it works for one value, it also works for the next value, then we'll be certain that it always works. What we a re saying is that if it works for n, then if we the next integer, n+1, we should get the value of the formula for S(n+1). Lets see if these \+ two are equal.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "S(n+1) = S(n) + (n+1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 33 "expand(lh s(%)) = expand(rhs(%)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 31 "verify(lhs(%), rhs(%), testeq);" }}}{PARA 0 "" 0 "" {TEXT -1 177 "\nT hey are! We have proven the formula is true for all integers n \263 1. This is, in essence, the method of mathematical induction. There are \+ two indispensable steps :\n " }{TEXT 266 223 "\n \+ Mathematical Induction - to Verify a Formula\n\n 1. Show t hat it works for at least one value of n\n 2. Show that whe never it works for a general value of n, it also works for the next va lue." }{TEXT -1 191 "\n\nThe first step is usually very easy - simply \+ plug in a value and show it works for that one value. The second step \+ involves expressing the same value in two different ways, as we did ab ove." }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 1 " " }{TEXT 262 30 "2. More Examples of Equalities" }}{PARA 0 "" 0 "" {TEXT -1 97 "\nHere is another example. Lets do this in a mo re streamlined way following the two steps above.\n\n" }{TEXT 267 19 " Example 2.1" }{TEXT -1 14 " : Prove that " }{XPPEDIT 18 0 "1/( 1*2);" "6#*&\"\"\"F$*&F$F$\"\"#F$!\"\"" }{TEXT -1 2 " +" }{XPPEDIT 18 0 "1/(2*3);" "6#*&\"\"\"F$*&\"\"#F$\"\"$F$!\"\"" }{TEXT -1 2 " +" } {XPPEDIT 18 0 "1/(3*4)" "6#*&\"\"\"F$*&\"\"$F$\"\"%F$!\"\"" }{TEXT -1 7 " +...+ " }{XPPEDIT 18 0 "1/(n*(n+1))" "6#*&\"\"\"F$*&%\"nGF$,&F&F$F $F$F$!\"\"" }{TEXT -1 3 " = " }{XPPEDIT 18 0 "n/(n+1)" "6#*&%\"nG\"\" \",&F$F%F%F%!\"\"" }{TEXT -1 68 " \n \+ is true for all integers n > 0.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 18 "S := n -> n/(n+1);" }}}{PARA 0 "" 0 "" {TEXT -1 18 " \n " }{TEXT 268 6 "Step 1" }{TEXT -1 19 " : Verify for n = 1" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 15 "S(1) = 1/(1*2);" } }}{PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 269 23 " Step 2 " }{TEXT -1 63 ": Show that the f ormula for S(n+1) holds if it holds for S(n). " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "S(n+1) = S(n) + 1/( (n+1)*( (n+1) + 1) );" }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "simplify(lhs(%)) = simplify( rhs(%)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "testeq( lhs(%) = rhs(%) );" }}}{PARA 0 "" 0 "" {TEXT -1 10 "\nDone!\n\n\n\n" }{TEXT 270 19 " Example 2.2" }{TEXT -1 4 " : " }{XPPEDIT 18 0 "1^3 + \+ 2^3 + 3^3 +" "6#,**$\"\"\"\"\"$F%*$\"\"#F&F%*$F&F&F%%#%?GF%" }{TEXT -1 8 " .... + " }{XPPEDIT 18 0 "n^3 " "6#*$%\"nG\"\"$" }{TEXT -1 2 "= \+ " }{XPPEDIT 18 0 "(1 + 2 + 3 + + n)^2" "6#*$,,\"\"\"F%\"\"#F%\"\"$ F%%#%?GF%%\"nGF%F&" }}{PARA 0 "" 0 "" {TEXT -1 251 "\nThis one is a li ttle trickier, because we can't simply add another term to find S(n+1) because S(n) is a square. To get around this, we can take the sqarero ot of S(n), add (n+1)^3, then square that result to demonstrate the ve racity of this formula.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "restart:\nS := n -> sum( k, k = 1..n)^2 ;" }}}{PARA 0 "" 0 "" {TEXT -1 18 "\n " }{TEXT 271 6 "Step 1" }{TEXT -1 19 " : Ver ify for n = 1" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "S(1) = 1^3; " }}}{PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 272 23 " Step 2 " }{TEXT -1 63 ": Show that the f ormula for S(n+1) holds if it holds for S(n). " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "S(n+1) = sqrt( S(n) + (n+1)^3) ^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "simplify(lhs(%)) = simplify(rhs(%)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "testeq( lhs(%) = rhs( %) );" }}}{PARA 0 "" 0 "" {TEXT -1 7 "\nDone!\n" }}{PARA 0 "" 0 "" {TEXT -1 2 "\n\n" }{TEXT 273 19 " Example 2.3" }{TEXT -1 14 " : Prove that " }{XPPEDIT 18 0 "1;" "6#\"\"\"" }{TEXT -1 2 " +" } {XPPEDIT 18 0 "2;" "6#\"\"#" }{TEXT -1 2 " +" }{XPPEDIT 18 0 "2^2;" "6 #*$\"\"#F$" }{TEXT -1 7 " +...+ " }{XPPEDIT 18 0 "2^n;" "6#)\"\"#%\"nG " }{TEXT -1 3 " = " }{XPPEDIT 18 0 "2^(n+1)-1;" "6#,&)\"\"#,&%\"nG\"\" \"F(F(F(F(!\"\"" }{TEXT -1 68 " \n is true for all integers n > 0.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "S := n -> 2^(n+1) - 1;" }}}{PARA 0 "" 0 "" {TEXT -1 18 "\n \+ " }{TEXT 274 6 "Step 1" }{TEXT -1 19 " : Verify for n = 1 " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 9 "S(1) = 1;" }}}{PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 275 23 " \+ Step 2 " }{TEXT -1 63 ": Show that the formula for S(n+1) holds if it holds for S(n). " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "S(n+1) = S(n) + 2^(n+1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "simplify(lhs(%)) = simplify(rhs(%)) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "testeq( lhs(%) = rhs(%) );" }}}{PARA 0 "" 0 "" {TEXT -1 7 "\nDone!\n" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 1 " " } {TEXT 263 27 "3. Induction & Inequalities" }}{PARA 0 "" 0 "" {TEXT -1 158 "\nWhen we are trying to prove an inequality rather than an equati on, we go through the same two general steps, but we can't express the result as a function.\n\n" }{TEXT 279 18 " Example 3.1" }{TEXT -1 16 " : Prove that " }{XPPEDIT 18 0 "2*n+1 <= n^2;" "6#1,&*&\"\"# \"\"\"%\"nGF'F'F'F'*$)F(F&F'" }{TEXT -1 28 " is true for all integer s " }{XPPEDIT 18 0 "n>=3" "6#1\"\"$%\"nG" }{TEXT -1 2 ".\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "Inequal := 2*n + 1 <= n^2;" }}} {PARA 0 "" 0 "" {TEXT -1 18 "\n " }{TEXT 280 6 "Step 1 " }{TEXT -1 69 " : Verify for n = 3 (the smaller number we can start a t in this case)" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "subs( n = 3, Inequal);\nverify(lhs(%), rhs(%) ,\{'less_than','equal'\});" }}} {PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 281 23 " Step 2 " }{TEXT -1 200 ": Show that the formul a for S(n+1) holds if it holds for S(n). Let's substitute n+1 for n, \+ in the left side of the inequality, \n with the hope of \+ showing it is less than the right side." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "LHS := subs( n = n+1, lhs(Inequal) );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "% = '(2*n + 1),` + `,2';" }}}{PARA 0 "" 0 "" {TEXT -1 95 "\n Since we know the the inequal ity is true for n, we can make this statement : \n" }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 18 "LHS < ''n^2 + 2'';" }}}{PARA 0 "" 0 "" {TEXT -1 35 " Also, by hypothesis :" }}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 6 "2 < n;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 12 "2 < 2*n + 1;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "'LHS' < 'n^2 + (2*n+1)';" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 30 "n^2 \+ + (2*n+1): % = factor(%) ;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 14 "LHS < (n+1)^2;" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "subs( n = n+1, Inequal);" }}}{PARA 0 "" 0 "" {TEXT -1 63 "So we have demons trated the inequality is also true for n+1!\n\n\n" }{TEXT 276 19 " \+ Example 3.2" }{TEXT -1 16 " : Prove that " }{XPPEDIT 18 0 "n^2 < = 2^n;" "6#1*$)%\"nG\"\"#\"\"\")F'F&" }{TEXT -1 26 " is true for all i ntegers " }{XPPEDIT 18 0 "n>=4" "6#1\"\"%%\"nG" }{TEXT -1 2 ".\n" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 22 "Inequal := n^2 <= 2^n;" }}} {PARA 0 "" 0 "" {TEXT -1 18 "\n " }{TEXT 277 6 "Step 1 " }{TEXT -1 19 " : Verify for n = 4" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "subs( n = 4, Inequal);\nverify(lhs(%), rhs(%) ,\{'les s_than','equal'\});" }}}{PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 278 23 " Step 2 " }{TEXT -1 63 ": Show that S(n+1) follows if S(n) is true. We can assume that " } {XPPEDIT 18 0 "n^2 <= 2^n" "6#1*$%\"nG\"\"#)F&F%" }{TEXT -1 1 "." }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 37 "LHS := subs( n = n+1, lhs(In equal) );" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }} }{PARA 0 "" 0 "" {TEXT -1 65 "\n Using the inequalit y above in example 3.1...." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 27 "LHS := %; LHS <= n^2 + n^2;" }}}{PARA 0 "" 0 "" {TEXT -1 39 " \+ Using the fact that " }{XPPEDIT 18 0 "n^2 <= 2^n" "6#1*$ %\"nG\"\"#)F&F%" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "2*n^2 <= \+ 2*(2^n);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 17 "2*n^2 <= 2^(n+1 );" }}}{PARA 0 "" 0 "" {TEXT -1 7 "\nDone!\n" }}{PARA 0 "" 0 "" {TEXT -1 3 "\n\n " }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 1 " " }{TEXT 264 15 " 4. Divisibility" }}{PARA 0 "" 0 "" {TEXT -1 134 "\nHere is another var iation - demonstrating that an expression is divisible by some number \+ for all integers plugged into the formula.\n\n" }{TEXT 282 18 " \+ Example 4.1" }{TEXT -1 15 " : Prove that " }{XPPEDIT 18 0 "n^3 + 14*n + 3" "6#,(*$%\"nG\"\"$\"\"\"*&\"#9F'F%F'F'F&F'" }{TEXT -1 43 " is div isible by 3 for all integers n > 0.\n" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 25 "S := n -> n^3 + 14*n + 3;" }}}{PARA 0 "" 0 "" {TEXT -1 18 "\n " }{TEXT 283 6 "Step 1" }{TEXT -1 19 " : Ver ify for n = 1" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "S(1);\n%/3; " }}}{PARA 0 "" 0 "" {TEXT -1 15 " " }}{PARA 0 "" 0 "" {TEXT 284 23 " Step 2 " }{TEXT -1 63 ": Show that the f ormula for S(n+1) holds if it holds for S(n). " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 7 "S(n+1);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}}{PARA 0 "" 0 "" {TEXT -1 85 "\n Lets take the difference of S(n+1) and S(n) - this will eliminate the " } {XPPEDIT 18 0 "n^3" "6#*$%\"nG\"\"$" }{TEXT -1 1 "." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 28 "difference := S(n+1) - S(n);" }}}{PARA 0 " " 0 "" {TEXT -1 85 " We expand the difference and find tha t each term is divisible by three! " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "expand(%);" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 4 "%/3;" }}}{PARA 0 "" 0 "" {TEXT -1 211 " This proves it. Do you see how? S(n+1) = S(n) + a polynomial divisible by three. Sinc e both polynomials \n on the right are divisible by 3, the n so is the left side, since they are equal." }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 24 "S(n+1) = 'S(n) + 3*(%)';" }}}{EXCHG }}{PARA 0 "" 0 "" {TEXT 259 36 "\n \251 2002 Waterloo Maple Inc " }}}{MARK "0 1" 9 }{VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }