CHAPTER 9: DISCRETE MATH - Kkuniyuk

(Chapter 9: Discrete Math) 9.14PART C : FORMULA FOR THE n th PARTIAL SUM OF ANARITHMETIC SEQUENCEThe n th partial sum of an arithmetic sequence with initial term a1 andcommon difference d is given by: a an Sn n 1 2 Think: The (cumulative) sum of the first n terms of an arithmetic sequence is givenby the number of terms involved times the average of the first and last terms.ExampleFind the 100th partial sum of the arithmetic sequence: 2, 5, 8, 11, SolutionWe found in the previous Example that: a100 299 a an Sn n 1 2 2 299 S100 100 2 ( ) 301 100 2 ( ) 15,050i.e., 2 5 8 . 299 15,050This is much easier than doing things brute force on your calculator!Read the Historical Note on p.628 in Larson for the story of how Gauss quickly100computed the sum of the first 100 positive integers, k 1 2 3 . 100 . Use ourk 1formula to confirm his result. Gauss’s trick is actually used in the proof of our formula;see p.694 in Larson. We will touch on a related question in Section 9.4.

(Chapter 9: Discrete Math) 9.15SECTION 9.3: GEOMETRIC SEQUENCES, PARTIAL SUMS, andSERIESPART A: WHAT IS A GEOMETRIC SEQUENCE?The following appears to be an example of a geometric sequence:a1 2a2 6a3 18a4 54 We begin with 2. After that, we successively multiply by 3 to obtain the other terms ofthe sequence. Recall that, for an arithmetic sequence, we successively add.A geometric sequence is determined by: Its initial termHere, it is a1 , although, in other examples, it could be a0 or something else.Here, a1 2 . Its common ratioThis is denoted by r. It is the number that we always multiply the previousterm by to obtain the following term. Here, r 3.Observe that: r a2a1 a3a2 ak 1ak( k Z ) The following information completely determines our sequence:The sequence is geometric.(Initial term) a1 2(Common ratio) r 3

(Chapter 9: Discrete Math) 9.16In general, a recursive definition for a geometric sequence that begins with a1 may begiven by: a1 given ak 1 ak r( k 1; "k is an integer" is implied )We assume a1 0 and r 0 .ExampleThe geometric sequence 2, 6, 18, 54, can be described by: a1 2 r 3

(Chapter 9: Discrete Math) 9.17PART B : FORMULA FOR THE GENERAL n th TERM OF AGEOMETRIC SEQUENCELet’s begin with a1 and keep multiplying by r until we obtain an expression for an ,where n Z .a1 a1a2 a1 ra3 a1 r 2a4 a1 r 3 an a1 r n 1The general n th term of a geometric sequence with initial term a1 andcommon ratio r is given by:an a1 r n 1Think: As with arithmetic sequences, we take n 1 steps to get from a1 to an .Note: Observe that the expression for an is exponential in n. This reflects the factthat geometric sequences often arise from exponential models, for example thoseinvolving compound interest or population growth.

(Chapter 9: Discrete Math) 9.18ExampleFind the 6th term of the geometric sequence: 2, 1 ,1, 2(Assume that 2 is the “first term.”)SolutionHere, a1 2 and r 1.2an a1 r n 1 1 a6 2 2 () 1 2 2 ()6 15 1 2 32 () 116Observe that, as n , the terms of this sequence approach 0.(Assume a1 0 . Then, a1 r n 1 0 as n ) ( 1 r 1)i.e., r 1

(Chapter 9: Discrete Math) 9.19PART C : FORMULA FOR THE n th PARTIAL SUM OF AGEOMETRIC SEQUENCEThe n th partial sum of a geometric sequence with initial term a1 and common ratio r(where r 1 ) is given by: 1 rn a1 a1r nSn or a1 1 r 1 r You should get used to summation notation:Remember that S n for a sequence starting with a1 is given by:Sn n ak 1k a1 a2 anBecause ak a1 r k 1 for our geometric series:Sn n a rk 1k 11a1 a1r n1 r a1 a1r a1r 2 . a1r n 1 a2a3an(according to our theorem in the box above)Note: The book Concrete Mathematics by Graham, Knuth, and Patashniksuggests a way to remember the numerator: “first in – first out.” This isbecause a1 is the “first” term included in the sum, while a1r n is the firstterm in the corresponding infinite geometric series that is excluded from thesum.1 rn2n 1Technical Note: The key is that 1 r r r . You can see that this1 ris true by multiplying both sides by 1 r . Also see the proof on p.694 of Larson.()Technical Note: If r 1, then we are dealing with a constant sequence andessentially a multiplication problem. For example, the 4th partial sum of the series7 7 7 7 . is 7 7 7 7 4 7 28 . In general, the n th partial sum of( )( )the series a1 a1 a1 . is given by na1 .

(Chapter 9: Discrete Math) 9.20ExampleFind the 6th partial sum of the geometric sequence 2, 1 ,1, 2Solution1for this sequence.21We found in the previous Example that: a6 16Recall that a1 2 and r We will use our formula to evaluate:S6 2 1 1111 24816Using our formula directly:Sn a1 a1r n1 r 1 rn or a1 1 r If we use the second version on the right 1 rn S n a1 1 r 6 1 1 2 S6 2 1 1 2 1 1 64 2 1 1 2

(Chapter 9: Discrete Math) 9.21 2 636432 2 12 64 3 1 322163 21 2 32 16 2116We can also use the first version and the “first in – first out” idea:S6 2 1 1111 24816“First out” is: a7 Sn 132a1 a1r n1 r12 32S6 1 1 2 64 1 32 32 63 3232 2116332162116 231

(Chapter 9: Discrete Math) 9.22PART D: INFINITE GEOMETRIC SERIESAn infinite series converges (i.e., has a sum) The S n partial sums approach a()real number as n , which is then called the sum of the series.In other words, if lim S n S , where S is a real number, then S is the sum of the series.n ExampleConsider the geometric series:1 1 1 1 .2 4 8 16Let’s take a look at the partial (cumulative) sums:1111 . 81624 1 2 S1 34 S2 78 S3 S4 1516It appears that the partial sums are approaching 1. In fact, they are; we willhave a formula for this. This series has a sum, and it is 1.The figure below may make you a believer:

(Chapter 9: Discrete Math) 9.23ExampleThe geometric series 2 6 18 54 . has no sum, because: lim S n n ExampleThe geometric series 1 1 1 1 . has no sum, because the partial sumsdo not approach a single real number. Observe:1 1 1 1 . S1 1 S2 0 S3 1 S4 0()An infinite geometric series converges 1 r 1 i.e., r 1Take another look at the Examples of this Part.It is true that an infinite geometric series converges Its terms approach 0.Warning: However, this cannot be said about series in general. For example, the 11 1famous harmonic series 1 does not converge, even though the2 3k 1 kterms of the series approach 0. In order for a series to converge, it is necessary butnot sufficient for the terms to approach 0.No infinite arithmetic sequence (such as 2 5 8 11 ) can have a sum, unlessyou include 0 0 0 . as an arithmetic sequence.

(Chapter 9: Discrete Math) 9.24The sum of a convergent infinite geometric series with initial term a1 andcommon ratio r , where 1 r 1, is given by: i.e., r 1S a11 rTechnical Note: This comes from our partial sum formula S n (a1 a1r n)1 rand thefact that a1r n 0 as n 0 if 1 r 1. i.e., r 1ExampleWrite 0.81 as a nice (simplified) fraction of the forminteger.integerRecall how the repeating bar works: 0.81 0.81818181.Note: In Arithmetic, you learned how to use long division to express a“nice” fraction as a repeated decimal; remember that rational numbers canalways be expressed as either a terminating or a “nicely” repeating decimal.Now, after all this time, you will learn how to do the reverse!Solution0.81 can be written as: 0.81 0.0081 0.000081 .Observe that this is a geometric series with initial term a1 0.81 andcommon ratio r 0.00811 0.01 ; because r 1 , the series0.81100converges.The sum of the series is given by:S a11 r 0.810.81 81 9 1 0.01 0.99 99 11

(Chapter 9: Discrete Math) 9.25Again, you should get used to summation notation: S a1r k 1k 1 ()() 0.81 0.01k 1 k 1911If you make the substitution i k 1, the summation form can berewritten as: ()()()()S 0.81 0.01k 1 0.81 0.01i 0k 1iIn Calculus, 0 is more common than 1 as a lower limit of summation.

(Chapter 9: Discrete Math) 9.26SECTION 9.4: MATHEMATICAL INDUCTIONWhat is the sum of the first n positive integers, where n Z ? In other words, what is1 2 3 . n ? According to our formula for the n th partial sum of an arithmetic sequence 1 n n n 1(see Section 9.2), the answer is: S n n 2 2 ()Handshake Problem (Cool, but Optional)There’s another way of seeing why this formula works out.Imagine n 1 people walking into a room one-by-one. Whenever a person walks into aroom, he/she must shake hands exactly once with every other person who is currently inthe room, and those are the only handshakes they make. The first person who walks intothe room shakes nobody’s hand, the second person shakes the first person’s hand, thethird person shakes the first two people’s hands, and so on, until the last person shakesthe other n people’s hands. This means that every distinct pair of people eventually shakehands exactly once. The total number of handshakes then equals the number of distinctpairs of people that can be formed from a group of n 1 people.We see that the number of handshakes equals both 1 2 3 . n and( n 1)! ( n 1)! ( n 1) n ( n 1)! n ( n 1) .22! (( n 1) 2 )! 2! ( n 1)!2 ( n 1)!n ( n 1)Therefore: 1 2 3 . n n 1 2 2In this section, we will use mathematical induction to prove that: 1 2 3 . n ()n n 12Mathematical induction is used to prove conjectures, statements that we believe to be true butare as yet unproven. Unfortunately, the method of mathematical induction cannot give us an n 1formula such as 1 2 3 . n ; we must first guess at such a formula by perhaps2working out a few cases and using trial-and-error. (For example, try out Problem #90 in Section9.2 on p.633 in Larson.) Induction is then used to verify our guess.()

(Chapter 9: Discrete Math) 9.27Induction is commonly used in Discrete Math and in Linear Algebra. It is even used incontinuous mathematics; in Calculus, for example, induction is used to prove integrationformulas involving powers of (or products of powers of) trig functions.The Domino ImageVisualize a half-line (or a “ray”) of infinitely many dominoes. When are we guaranteedthat all the dominoes will eventually fall? If we are guaranteed the following: The first domino falls.(This corresponds to the Basis Step.) The fall of one domino guarantees the fall of the next domino.(This corresponds to the Inductive Step.)The Proof of Our FormulaConjecture:()The following is true for all positive integers n i.e., n Z :Pn , which states that: 1 2 3 . n ()n n 12Basis Step:Verify that P1 is true. (i.e., Verify that Pn is true for n 1 .)1 1 ()1 1 1212()21 1This demonstrates that P1 is true, because we have shown that P1 isequivalent to the true statement 1 1.

(Chapter 9: Discrete Math) 9.28Note: If we only had to prove Pn for all integers n such that n 7 , say, then wewould verify P7 as our Basis Step.Inductive Step:Let k be any fixed positive integer. (Some books use n; whatever you do, beconsistent throughout the problem!)Assume that Pk is true. (This assumption is called the Inductive Hypothesis, whichwe will abbreviate as I.H.)Using the Domino Image: Assume that the k th domino has fallen.Here, we assume: 1 2 3 . k ()k k 12Show that Pk 1 is then true.()Using the Domino Image: We must then show that the k 1stdomino mustthen fall as a result.Here, we must show that, as a result:k 1) (( k 1) 1)(( k 1) ( k 2)1 2 3 . ( k 1) , or22This is somewhat similar to a verification problem in trig in that the righthand side is something of a TARGET.

(Chapter 9: Discrete Math) 9.29()()1 2 3 . k 1 1 2 3 . k k 1Apply the I.H. to this. () k k 1( k 1)) 2 ( k 1)2k k 1(22k k 1 2 k 1(() (2k 2 k 1)())2( from Factoring )2( TARGET )( k 1) ( k 2)Note: The argument above works even for k 1 , k 2 , and k 3 , eventhough the first line may seem incompatible with those cases.ConclusionWe may now write: Pn is true for all positive integers n.orPn is true for all positive integers n. QED.Note: QED stands for the Latin phrase Quod Erat Demonstrandum.It effectively means “that which was to have been proven.”Read p.648 in Larson for formulas for sums of powers of the first n positive integers.Challenge ProblemUse induction to prove that every amount of postage greater than or equal to 12 cents canbe formed by using just 4- and 5-cent stamps.

(Chapter 9: Discrete Math) 9.30SECTION 9.5: THE BINOMIAL THEOREMPART A: INTRO()nHow do we expand a b , where n is a nonnegative integer?(a b)0 1(a b)1 a b(a b)2 a 2 2ab b2(a b)3 ( a b) ( a b )2Do first2 a 3a b 3ab2 b3 3(a b)10 YUK!Look for patternsTake (a b) . Let’s look at the variable parts of the terms.3(a b)322 a 3 3a b 3abb3 Startswitha3Endswithb3At each step, the exponent on a by 1 the exponent on b by 1a 0 1, b 0 1, so they are “invisible.”Each term has degree 3.

(Chapter 9: Discrete Math) 9.31In general,(a b)n a n b n (n is a whole number) ( n 1) terms(# terms power 1)What about the coefficients? They are given by PART B: PASCAL’S TRIANGLEThe ingredients:“Tent” of “1”sAny other entry sum of the two entries immediately aboveRow n gives the coefficients for (a b) .n(a b) 0 1(a b)1 a b(a b) 2 a 2 2ab b 2(a b) 3 a 3 3a 2b 3ab 2 b 3(a b)4 a 4 4a 3b 6a 2b 2 4ab3 b4 (See my website for some magical properties of Pascal’s triangle!)

(Chapter 9: Discrete Math) 9.32PART C: EXPANDING POWERS OF GENERAL BINOMIALSExampleExpand and simplify (3x y) using the Binomial Theorem.3Solution3We will use the template for a b .(3x y)3 3x ( y) SubSub a 3 xb y [a b]33 a 3 3a 2 b 3ab 2 b 3Sub back: a (3x), b ( y) (3x) 3 3( 3x )2 ( y) 3(3x)( y) ( y)Simplify. First, do powers.2( )( ) 27x 3 3 9x 2 ( y) 3(3x) y 2 y3 27x 3 27x 2 y 9xy 2 y 33

THE MAGIC OF PASCAL'S TRIANGLEPASCAL'S TRIANGLEÊ nˆThis represents a way to write down the "early" binomial coefficients Á easily.Ër Each row begins and ends with "1". (We have a "tent" of "1"s.) Every other entry equals the sum of the two entries immediately above it.Here it is:111111234136141Ê 0ˆRow 0: Contains Á Ë 0 Ê1 ˆ Ê1ˆRow 1: Contains Á , Á Ë 0 Ë1 Ê 2 ˆ Ê 2ˆ Ê 2ˆRow 2: Contains Á , Á , Á Ë 0 Ë1 Ë 2 Ê 3ˆ Ê 3ˆ Ê 3ˆ Ê 3ˆRow 3: Contains Á , Á , Á , Á Ë 0 Ë1 Ë 2 Ë 3 Ê 4ˆ Ê 4ˆ Ê 4ˆ Ê 4ˆ Ê 4ˆRow 4: Contains Á , Á , Á , Á , Á Ë 0 Ë 1 Ë 2 Ë 3 Ë 4 etc. - The "histograms" of the rows approach a bell-shaped "normal" distribution!We can observe some basic properties of binomial coefficients:Ê nˆ Ê n ˆSymmetry about the center: Á Á Ë r Ë n - r (The process of choosing r winners is equivalent to the process ofchoosing n-r losers.)Ê nˆ Ê nˆThe "tent" of "1"s: Á Á 1Ë 0 Ë n Ê nˆ Ê n ˆThe "inner tent" of natural numbers: Á Á nË1 Ë n - 1 (There are n ways to get one winner and n-1 losers from a group of npeople.)

THE PLINKO / PACHINKO APPROACH TO PASCAL'S TRIANGLEIn the game of Plinko on the CBS game show "The Price is Right", contestants wonmoney by standing over a board full of pins and dropping chips. The chips then fell intobins at the bottom of the board; each bin was labeled with a dollar amount that was addedto the contestant's winnings.Now imagine a pinboard shaped like Pascal's triangle:Player After pin is hit, the chip can move left or right.111112 After a pin is hit, the chip can move left or right.1334 After a pin is hit, the chip can move left or right.1 After a pin is hit, the chip can move left or right.161 After a pin is hit, the chip can move left or right.4It turns out that the number of ways to hit a pin is equal to the number on the pin!ExampleThere are 3 ways to hit the boldfaced pin labeled "3" above.One way: LLR12111 Left (L) - first "drop"11334 Left (L) - second "drop"16 Right (R) - third "drop"141A second way: LRL111111 Right (R)12334 Left (L)6 Left (L)141

A third way: RLL11111 Right (R)1334 Left (L)126 Left (L)141The only way to reach the "3" is if there are exactly one "R" and two "L"sin any order. How many ways are there to choose exactly one of the threeÊ 3ˆdrops to be an "R"? Á , which the 3 represents!Ë1 Likewise, there are 6 ways to hit the "6" pin, because out of four drops, weÊ 4ˆneed exactly two of them to be "R"s. There are Á 6 ways to do this.Ë 2 Remember the construction of Pascal's triangle: Each row begins and ends with "1". (We have a "tent" of "1"s.) Every other entry equals the sum of the two entries immediately above it.How does the Plinko model exhibit this?Example111111233416141There is 1 way to hit the "1" (all "L"s).Then, you can move right to hit the "4".There are 3 ways to hit the "3".Then, you can move left to hit the "4".So, there are 4 total ways to hit the "4".Note: If you go to a science museum that has a "Plinko-type" board with numerous ballsbeing dropped from the top-center, the bottom of the board should look like a bell curve!

EXPANDING POWERS OF BINOMIALS: THE BINOMIAL THEOREM(MATH 96)Remember that Row n of Pascal's Triangle provides the coefficients for the expansion of( a b )n :Ê nˆÊ nˆÊ nˆÊ nˆ(a b)n Á a n Á a n -1b Á a n - 2 b 2 . Á b nË 0 Ë1 Ë 2 Ë n Example(a b)3 1a 3 3a 2 b 3ab 2 1b 3Here's why this expansion of ( a b) is correct:3You can start by writing down 8 terms, each corresponding to a sequence ofchoices.3a b) ( a b) ( a b)(a b) 12(443 124 43 124 43Choose Choose C

Calculus tends to deal more with "continuous" mathematics than "discrete" mathematics. What is the difference? Analogies may help the most. Discrete is digital; continuous is analog. Discrete is a dripping faucet; continuous is running water. Discrete math tends to deal with things that you can "list," even if the list is infinitely .