#set document(title: "3.6 Chapter Summary", author: "OpenStax / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 3.6#h(0.6em)Chapter Summary #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ Each day your supply of magic chocolate covered espresso beans doubles (each one splits in half), but then you eat 5 of them. You have 10 at the start of day 0. + Write out the first few terms of the sequence. Then give a recursive definition for the sequence and explain how you know it is correct. + Prove, using induction, that the last digit of the number of beans you have on the #math.equation(block: false, alt: "n")[$n$]th day is always a 5 for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$]. + Find a closed formula for the #math.equation(block: false, alt: "n")[$n$]th term of the sequence and prove it is correct by induction. ] In this chapter we explored sequences and mathematical induction. At first these might not seem entirely related, but there is a link: recursive reasoning. When we have many cases (maybe infinitely many), it is often easier to describe a particular case by saying how it relates to other cases, instead of describing it absolutely. For sequences, we can describe the #math.equation(block: false, alt: "n")[$n$]th term in the sequence by saying how it is related to the #emph[previous] term. When showing a statement involving the variable #math.equation(block: false, alt: "n")[$n$] is true for all values of #math.equation(block: false, alt: "n")[$n$], we can describe why the case for #math.equation(block: false, alt: "n equals k")[$n = k$] is true on the basis of why the case for #math.equation(block: false, alt: "n equals k minus 1")[$n = k − 1$] is true. While thinking of problems recursively is often easier than thinking of them absolutely (at least after you get used to thinking in this way), our ultimate goal is to move beyond this recursive description. For sequences, we want to find #emph[closed formulas] for the #math.equation(block: false, alt: "n")[$n$]th term of the sequence. For proofs, we want to know the statement is actually true for a particular #math.equation(block: false, alt: "n")[$n$] (not only under the assumption that the statement is true for the previous value of #math.equation(block: false, alt: "n")[$n$]). In this chapter we saw some methods for moving from recursive descriptions to absolute descriptions. - If the terms of a sequence increase by a constant difference or constant ratio (these are both recursive descriptions), then the sequences are arithmetic or geometric, respectively, and we have closed formulas for each of these based on the initial terms and common difference or ratio. - If the terms of a sequence increase at a polynomial rate (that is, if the differences between terms form a sequence with a polynomial closed formula), then the sequence is itself given by a polynomial closed formula (of degree one more than the sequence of differences). - If the terms of a sequence increase at an exponential rate, then we expect the closed formula for the sequence to be exponential. These sequences often have relatively nice recursive formulas, and the #emph[characteristic root technique] allows us to find the closed formula for these sequences. - If we want to prove that a statement is true for all values of #math.equation(block: false, alt: "n")[$n$] (greater than some first small value), and we can describe why the statement being true for #math.equation(block: false, alt: "n equals k")[$n = k$] implies the statement is true for #math.equation(block: false, alt: "n equals k plus 1")[$n = k + 1$], then the #emph[principle of mathematical induction] gives us that the statement is true for all values of #math.equation(block: false, alt: "n")[$n$] (greater than the base case). Throughout the chapter we tried to understand #emph[why] these facts listed above are true. In part, that is what proofs, by induction or not, attempt to accomplish: they explain why mathematical truths are in fact truths. As we develop our ability to reason about mathematics, it is a good idea to make sure that the methods of our reasoning are sound. The branch of mathematics that deals with deciding whether reasoning is good or not is #emph[mathematical logic], the subject of the next chapter. === Chapter Review Consider the sequence #math.equation(block: false, alt: "5 , 11 , 19 , 29 , 41 , 55 , and so on")[$5 , 11 , 19 , 29 , 41 , 55 , …$]. Assume #math.equation(block: false, alt: "a sub 1 equals 5")[$a_(1) = 5$]. + Find a closed formula for #math.equation(block: false, alt: "a sub n")[$a_(n)$], the #math.equation(block: false, alt: "n")[$n$]th term of the sequence, by writing each term as a sum of a sequence. Hint: first find #math.equation(block: false, alt: "a sub 0")[$a_(0)$], but ignore it when collapsing the sum. + Find a closed formula again, this time using either polynomial fitting or the characteristic root technique (whichever is appropriate). Show your work. + Find a closed formula once again, this time by recognizing the sequence as a modification to some well known sequence(s). Explain. Suppose the closed formula for a particular sequence is a degree 3 polynomial. What can you say about the closed formula for: + The sequence of partial sums. + The sequence of second differences. #solutionbox[ + The sequence of partial sums will be a degree 4 polynomial (its sequence of differences will be the original sequence). + The sequence of second differences will be a degree 1 polynomial - an arithmetic sequence. ] Consider the sequence given recursively by #math.equation(block: false, alt: "a sub 1 equals 4")[$a_(1) = 4$], #math.equation(block: false, alt: "a sub 2 equals 6")[$a_(2) = 6$] and #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus a sub n minus 2")[$a_(n) = a_(n − 1) + a_(n − 2)$]. + Write out the first 6 terms of the sequence. + Could the closed formula for #math.equation(block: false, alt: "a sub n")[$a_(n)$] be a polynomial? Explain. #solutionbox[ + #math.equation(block: false, alt: "4 , 6 , 10 , 16 , 26 , 42 , and so on")[$4 , 6 , 10 , 16 , 26 , 42 , …$]. + No, taking differences gives the original sequence back, so the differences will never be constant. ] The sequence #math.equation(block: false, alt: "open parenthesis a sub n close parenthesis sub n greater than or equal to 1")[$( a_(n) )_(n ≥ 1)$] starts #math.equation(block: false, alt: "minus 1 , 0 , 2 , 5 , 9 , 14 and so on")[$− 1 , 0 , 2 , 5 , 9 , 14 …$] and has closed formula #math.equation(block: false, alt: "a sub n equals the fraction open parenthesis n plus 1 close parenthesis open parenthesis n minus 2 close parenthesis over 2")[$a_(n) = display(frac(( n + 1 ) ( n − 2 ), 2))$]. Use this fact to find a closed formula for the sequence #math.equation(block: false, alt: "open parenthesis b sub n close parenthesis sub n greater than or equal to 1")[$( b_(n) )_(n ≥ 1)$] which starts #math.equation(block: false, alt: "4 , 10 , 18 , 28 , 40 , and so on")[$4 , 10 , 18 , 28 , 40 , …$]. #math.equation(block: false, alt: "b sub n equals")[$b_(n) =$] \_\_\_\_\_ #solutionbox[ #math.equation(block: true, alt: "b sub n equals open parenthesis n plus 3 close parenthesis n")[$b_(n) = ( n + 3 ) n$]. ] The in song #emph[The Twelve Days of Christmas], my true love gave to me first 1 gift, then 2 gifts and 1 gift, then 3 gifts, 2 gifts and 1 gift, and so on. How many gifts did my true love give me all together during the twelve days? Your magic chocolate bunnies reproduce like rabbits: every large bunny produces 2 new mini bunnies each day, and each day every mini bunny born the previous day grows into a large bunny. Assume you start with 2 mini bunnies and no bunny ever dies (or gets eaten). + Write out the first few terms of the sequence. + Give a recursive definition of the sequence and explain why it is correct. + Find a closed formula for the #math.equation(block: false, alt: "n")[$n$]th term of the sequence. #solutionbox[ + On the first day, your 2 mini bunnies become 2 large bunnies. On day 2, your two large bunnies produce 4 mini bunnies. On day 3, you have 4 mini bunnies (produced by your 2 large bunnies) plus 6 large bunnies (your original 2 plus the 4 newly matured bunnies). On day 4, you will have #math.equation(block: false, alt: "12")[$12$] mini bunnies (2 for each of the 6 large bunnies) plus 10 large bunnies (your previous 6 plus the 4 newly matured). The sequence of total bunnies is #math.equation(block: false, alt: "2 , 2 , 6 , 10 , 22 , 42 and so on")[$2 , 2 , 6 , 10 , 22 , 42 …$] starting with #math.equation(block: false, alt: "a sub 0 equals 2")[$a_(0) = 2$] and #math.equation(block: false, alt: "a sub 1 equals 2")[$a_(1) = 2$]. + #math.equation(block: false, alt: "a sub n equals a sub n minus 1 plus 2 a sub n minus 2")[$a_(n) = a_(n − 1) + 2 a_(n − 2)$]. This is because the number of bunnies is equal to the number of bunnies you had the previous day (both mini and large) plus 2 times the number you had the day before that (since all bunnies you had 2 days ago are now large and producing 2 new bunnies each). + Using the characteristic root technique, we find #math.equation(block: false, alt: "a sub n equals a 2 to the power n plus b open parenthesis minus 1 close parenthesis to the power n")[$a_(n) = a 2^(n) + b ( − 1 )^(n)$], and we can find #math.equation(block: false, alt: "a")[$a$] and #math.equation(block: false, alt: "b")[$b$] to give #math.equation(block: false, alt: "a sub n equals the fraction 4 over 32 to the power n plus the fraction 2 over 3 open parenthesis minus 1 close parenthesis to the power n")[$a_(n) = frac(4, 3) 2^(n) + frac(2, 3) ( − 1 )^(n)$]. ] Consider the sequence of partial sums of #emph[squares] of Fibonacci numbers: #math.equation(block: false, alt: "F sub 1 squared")[$F_(1)^(2)$], #math.equation(block: false, alt: "F sub 1 squared plus F sub 2 squared")[$F_(1)^(2) + F_(2)^(2)$], #math.equation(block: false, alt: "F sub 1 squared plus F sub 2 squared plus F sub 3 squared , and so on")[$F_(1)^(2) + F_(2)^(2) + F_(3)^(2) , …$]. The sequences starts #math.equation(block: false, alt: "1 , 2 , 6 , 15 , 40 , and so on")[$1 , 2 , 6 , 15 , 40 , …$] + Guess a formula for the #math.equation(block: false, alt: "n")[$n$]th partial sum, in terms of Fibonacci numbers. Hint: write each term as a product. + Prove your formula is correct by mathematical induction. + Explain what this problem has to do with the following picture: #figure(figph[A rectangle divided into six squares of decreasing size that spiral inward. One large square fills the left portion of the rectangle. The strip remaining on the right is divided into a square below, a smaller square above it, then a smaller square again, and finally two of the smallest squares filling the last corner.], alt: "A rectangle divided into six squares of decreasing size that spiral inward. One large square fills the left portion of the rectangle. The strip remaining on the right is divided into a square below, a smaller square above it, then a smaller square again, and finally two of the smallest squares filling the last corner.", caption: none) Prove the following statements by mathematical induction: + #math.equation(block: false, alt: "n ! less than n to the power n")[$n ! < n^(n)$] for #math.equation(block: false, alt: "n greater than or equal to 2")[$n ≥ 2$] + #math.equation(block: false, alt: "the fraction 1 over 1 times 2 plus the fraction 1 over 2 times 3 plus the fraction 1 over 3 times 4 plus ⋯ plus the fraction 1 over n times open parenthesis n plus 1 close parenthesis equals the fraction n over n plus 1")[$display(frac(1, 1 ⋅ 2) + frac(1, 2 ⋅ 3) + frac(1, 3 ⋅ 4) + ⋯ + frac(1, n ⋅ ( n + 1 )) = display(frac(n, n + 1)))$] for all #math.equation(block: false, alt: "n ∈ Z to the power plus")[$n ∈ Z^(+)$]. + #math.equation(block: false, alt: "4 to the power n minus 1")[$4^(n) − 1$] is a multiple of 3 for all #math.equation(block: false, alt: "n ∈ N")[$n ∈ N$]. + The #emph[greatest] amount of postage you #emph[cannot] make exactly using 4 and 9 cent stamps is 23 cents. + Every even number squared is divisible by 4. + Hint: #math.equation(block: false, alt: "open parenthesis n plus 1 close parenthesis to the power n plus 1 greater than open parenthesis n plus 1 close parenthesis times n to the power n")[$( n + 1 )^(n + 1) > ( n + 1 ) ⋅ n^(n)$]. + Hint: This should be similar to the other sum proofs. The last bit comes down to adding fractions. + Hint: Write #math.equation(block: false, alt: "4 to the power k plus 1 minus 1 equals 4 times 4 to the power k minus 4 plus 3")[$4^(k + 1) − 1 = 4 ⋅ 4^(k) − 4 + 3$]. + Hint: one 9-cent stamp is 1 more than two 4-cent stamps, and seven 4-cent stamps is 1 more than three 9-cent stamps. + Careful to actually use induction here. The base case: #math.equation(block: false, alt: "2 squared equals 4")[$2^(2) = 4$]. The inductive case: assume #math.equation(block: false, alt: "open parenthesis 2 n close parenthesis squared")[$( 2 n )^(2)$] is divisible by 4 and consider #math.equation(block: false, alt: "open parenthesis 2 n plus 2 close parenthesis squared equals open parenthesis 2 n close parenthesis squared plus 4 n plus 4")[$( 2 n + 2 )^(2) = ( 2 n )^(2) + 4 n + 4$]. This is divisible by 4 because #math.equation(block: false, alt: "4 n plus 4")[$4 n + 4$] clearly is, and by our inductive hypothesis, so is #math.equation(block: false, alt: "open parenthesis 2 n close parenthesis squared")[$( 2 n )^(2)$]. Prove #math.equation(block: false, alt: "1 cubed plus 2 cubed plus 3 cubed plus ⋯ plus n cubed equals open parenthesis the fraction n open parenthesis n plus 1 close parenthesis over 2 close parenthesis squared")[$1^(3) + 2^(3) + 3^(3) + ⋯ + n^(3) = attach(( frac(n ( n + 1 ), 2) ), t: 2)$] holds for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$], by mathematical induction. This is a straight forward induction proof. Note you will need to simplify #math.equation(block: false, alt: "open parenthesis the fraction n open parenthesis n plus 1 close parenthesis over 2 close parenthesis squared plus open parenthesis n plus 1 close parenthesis cubed")[$attach(( frac(n ( n + 1 ), 2) ), t: 2) + ( n + 1 )^(3)$] and get #math.equation(block: false, alt: "open parenthesis the fraction open parenthesis n plus 1 close parenthesis open parenthesis n plus 2 close parenthesis over 2 close parenthesis squared")[$attach(( frac(( n + 1 ) ( n + 2 ), 2) ), t: 2)$]. Suppose #math.equation(block: false, alt: "a sub 0 equals 1")[$a_(0) = 1$], #math.equation(block: false, alt: "a sub 1 equals 1")[$a_(1) = 1$] and #math.equation(block: false, alt: "a sub n equals 3 a sub n minus 1 minus 2 a sub n minus 1")[$a_(n) = 3 a_(n − 1) − 2 a_(n − 1)$]. Prove, using strong induction, that #math.equation(block: false, alt: "a sub n equals 1")[$a_(n) = 1$] for all #math.equation(block: false, alt: "n")[$n$]. There are two base cases #math.equation(block: false, alt: "P open parenthesis 0 close parenthesis")[$P ( 0 )$] and #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$]. Then, for the inductive case, assume #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for all #math.equation(block: false, alt: "k less than n")[$k < n$]. This allows you to assume #math.equation(block: false, alt: "a sub n minus 1 equals 1")[$a_(n − 1) = 1$] and #math.equation(block: false, alt: "a sub n minus 2 equals 1")[$a_(n − 2) = 1$]. Apply the recurrence relation. Prove using induction that every set containing #math.equation(block: false, alt: "n")[$n$] elements has #math.equation(block: false, alt: "2 to the power n")[$2^(n)$] different subsets for any #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$]. #solutionbox[ Let #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] be the statement, “every set containing #math.equation(block: false, alt: "n")[$n$] elements has #math.equation(block: false, alt: "2 to the power n")[$2^(n)$] different subsets.” We will show #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$]. Base case: Any set with 1 element #math.equation(block: false, alt: "open brace a close brace")[$\{ a \}$] has exactly 2 subsets: the empty set and the set itself. Thus the number of subsets is #math.equation(block: false, alt: "2 equals 2 to the power 1")[$2 = 2^(1)$]. Thus #math.equation(block: false, alt: "P open parenthesis 1 close parenthesis")[$P ( 1 )$] is true. Inductive case: Suppose #math.equation(block: false, alt: "P open parenthesis k close parenthesis")[$P ( k )$] is true for some arbitrary #math.equation(block: false, alt: "k greater than or equal to 1")[$k ≥ 1$]. Thus every set containing exactly #math.equation(block: false, alt: "k")[$k$] elements has #math.equation(block: false, alt: "2 to the power k")[$2^(k)$] different subsets. Now consider a set containing #math.equation(block: false, alt: "k plus 1")[$k + 1$] elements: #math.equation(block: false, alt: "A equals open brace a sub 1 , a sub 2 , and so on , a sub k , a sub k plus 1 close brace")[$A = \{ a_(1) , a_(2) , … , a_(k) , a_(k + 1) \}$]. Any subset of #math.equation(block: false, alt: "A")[$A$] must either contain #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$] or not. In other words, a subset of #math.equation(block: false, alt: "A")[$A$] is just a subset of #math.equation(block: false, alt: "open brace a sub 1 , a sub 2 , and so on , a sub k close brace")[$\{ a_(1) , a_(2) , … , a_(k) \}$] with or without #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$]. Thus there are #math.equation(block: false, alt: "2 to the power k")[$2^(k)$] subsets of #math.equation(block: false, alt: "A")[$A$] which contain #math.equation(block: false, alt: "a sub k plus 1")[$a_(k + 1)$] and another #math.equation(block: false, alt: "2 to the power k plus 1")[$2^(k + 1)$] subsets of #math.equation(block: false, alt: "A")[$A$] which do not contain #math.equation(block: false, alt: "a to the power k plus 1")[$a^(k + 1)$]. This gives a total of #math.equation(block: false, alt: "2 to the power k plus 2 to the power k equals 2 times 2 to the power k equals 2 to the power k plus 1")[$2^(k) + 2^(k) = 2 ⋅ 2^(k) = 2^(k + 1)$] subsets of #math.equation(block: false, alt: "A")[$A$]. But our choice of #math.equation(block: false, alt: "A")[$A$] was arbitrary, so this works for any subset containing #math.equation(block: false, alt: "k plus 1")[$k + 1$] elements, so #math.equation(block: false, alt: "P open parenthesis k plus 1 close parenthesis")[$P ( k + 1 )$] is true. Therefore, by the principle of mathematical induction, #math.equation(block: false, alt: "P open parenthesis n close parenthesis")[$P ( n )$] is true for all #math.equation(block: false, alt: "n greater than or equal to 1")[$n ≥ 1$]. ]