### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# LINEAR ALGEBRA Math 6

UCI

GPA 3.73

### View Full Document

## 22

## 0

## Popular in Course

## Popular in Mathematics (M)

This 65 page Class Notes was uploaded by Adam Crona on Saturday September 12, 2015. The Class Notes belongs to Math 6 at University of California - Irvine taught by Staff in Fall. Since its upload, it has received 22 views. For similar materials see /class/201872/math-6-university-of-california-irvine in Mathematics (M) at University of California - Irvine.

## Reviews for LINEAR ALGEBRA

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15

Jim Lambers Math 6A Spring Quarter 200304 Lecture 21 Examples These examples correspond to Section 32 in the text Example The set of integers Z is countable To see this we note that a bijection between N and Z can be explicitly constructed The function f Z a N de ned by 22 iszO fz72271if2lt07 2627 has the inverse f l N a Z given by 1 7 712 ifniseven f 7n12 ifnisodd 39 That these functions are inverses can be seen by computing ff 1n and f 1fz and verifying that they are equal to n and 2 respectively B Example The set of rational numbers Q is countable This can be seen by writing the positive rational numbers on an in nite grid starting at the upper left corner and writing numbers on diagonals further and further away from the corner in such a way that the numbers on each diagonal have the same sum of their numerator and denominator This grid begins as follows 11 21 31 41 51 61 12 22 32 42 52 13 23 33 43 14 24 34 By writing the positive rational numbers in this order we can be sure to list all of them If we associate positive integers with these rational numbers as follows 1141 2143 31H6 4lgt10 51415 61421 1242 2245 3249 42414 52420 1344 2348 33413 43419 1447 24412 34418 15411 25417 16H16 Jim Lambers Math 6A Spring Quarter 200304 Lecture 21 Notes These notes correspond to Section 34 in the text Recursive De nitions and Structural Induction While it is commonplace to de ne objects in terms of other objects it is sometimes useful to de ne objects in terms of objects of the same type Such a de nition is called a recursive de nition Example Previously we de ned an r permutation to be an ordered collection of r elements How ever given a set S containing n elements we can also de ne an r permutation of elements of S to be an r 7 1 permutation of elements of S with one element of S added This recursive de nition is more natural for implementing a computer program that iterates over all possible permutations since a procedure that generates r permutations where r is an input to the procedure can simply call itself with the input r 7 1 If r 1 then a permutation simply consists of a single element of S D In this lecture we will discuss various discrete structures and learn how to de ne them and work with them recursively Recursively De ned Functions To this point we have de ned functions explicitly using a formula that describes how the image of each element of the domain is determined in terms of the element itself In some cases however it is easier to describe how a function f A a B assigns an element y E B to an element x E A in terms of other elements in the range of 1 rather than in terms of m In the case where A N the set of natural numbers one can rst explicitly de ne fn where n O This step is called the basis step corresponding to the basis step of mathematical induction Then we can de ne fn for larger values of n in terms of its values for smaller values of n This step is called the recursive step corresponding to the inductive step in mathematical induction A de nition of this form is called a recursive de nition or an inductive de nition Example Let an io be a sequence The series can be de ned recursively as follows 0 Basis Step So 2290 a a0 0 Recursiue Step For each n 2 O we have n1 n Sn1 Zai at an1 Sn an1 i0 i0 One of the most well known recursively de ned functions is the sequence of Fibonacci numbers which we now de ne De nition Fibonacci Numbers The Fibonacci numbers are the numbers in the sequence f0 f1 f2 de ned by f007 1317 infn71fn727 7122 Remark Note that in this de nition the values of f0 and f1 are both de ned explicitly In general one can explicitly de ne any number of function values in the basis step However for the de nition to be considered a recursive de nition there must exist some nonnegative integer no such that for all n 2 n0 fn is de ned in the recursive step in terms of values of the form fk where k is an integer D This recursive de nition of the Fibonacci numbers is an example of a recurrence relation which we will study further in upcoming lectures This de nition is more intuitive than the explicit de nition of 1 which is f 7 1 1 V5 7 1 17 n J5 2 5 2 39 In particular it is counterintuitive that this explicit formula would yield integers for each natural number n but it is clear from the recursive de nition that each Fibonacci number is an integer Recursively De ned Sets and Structures Recursion can be used to de ne some of the most fundamental structures used in computer science We will now formally introduce a number of these structures Their recursive de nitions suggest recursive algorithms for working with these structures As we have seen these algorithms can be obtained and proven correct using t induction This between recursion and induction is natural for two reasons 0 Both processes work with instantiations of a concept such as de nition or a statement that correspond in some way to the set of natural numbers In the case of induction we are proving that a statement Pn is true for each natural number n while in the case of recursion we are de ning objects using n applications of speci ed rules for any natural number n Both processes relate instantiations corresponding to larger numbers to those corresponding to smaller numbers In proofs using induction a statement Pn is shown to be true given that Pn 1 is true In a recursive de nition objects constructed using n applications of the rules of the de nition are de ned in terms of objects constructed using n 7 1 applications 0 Both processes rely on some base instantiation typically corresponding to n 0 as a foundation on which to perform tasks such as de ning objects or forming mathematical ar guments Strings In the previous lecture we considered sequences of elements and focused on cases in which the elements were numbers A string is a nite sequence whose terms are elements of a set called an alphabet which is a set of symbols or characters such as letters We can use recursion to de ne the set of all strings composed of characters from a given alphabet De nition Strings Let 2 be an alphabet The set of strings over the alphabet 2 denoted by 2 is de ned recursively by 0 Basis Step 662 where 6 denotes the empty string which is the string containing no symbols 0 Recursive Step Ifw E 2 and z E 2 then wm E 2 Example Let 2 a b c d z yz the set of all letters in the English alphabet Then all words in the English language belong to 2 such as words belong and language However not all strings in 2 are valid words in the English language For instance zzzzzmyyyyy E 2 so it is a string over 2 even though it is not a word D The preceding de nition shows how strings can be constructed by adding one character at a time Strings can also be constructed from other strings using an operation called concatenation which we now de ne De nition Concatenation Let 2 be an alphabet and let u and U be strings in 2 The concate nation ofu and U denoted by up or u 11 is a string in 2 that is de ned recursively by 0 Basis Step Ifw E 2 then we w where e is the empty string 0 Recursive Step If w1 E 2 wg E 2 and z E 2 then w1w2z w1w2z Example The concatenation of the strings float and ing denoted by float ing is the string floating Note that concatenation is not commutative as ing float ingfloat However it is associative as re cursive ly re cursive ly recursively D Trees One of the most fundamental data structures in computer science is a graph which is used to describe relationships among objects We now consider certain types of graphs that are called trees Trees in particular are used to describe a hierarchy of objects One object in the tree called the root is at the top of the hierarchy in some sense and it is directly related to the next highest objects in the hierarchy which are in turn related to the next highest objects and so on down to the lowest level objects which are called leaves We now de ne these structures precisely using recursion De nition Rooted Trees A graph is a set consisting of vertices or nodes and edges that are pairs of vertices A rooted tree is a graph in which one vertex is designated as the root and the structure of the graph is de ned recursively by 0 Basis Step A single vertex is a rooted tree 0 Recursive step If T1T2 Tn are rooted trees with roots r1 r2 rn respectively and r is a root that does not belong to any of the trees T1 T2 Tn then the graph consisting of T1T2 Tn the root r and edges between r and each of the roots r1r2 rn is a rooted tree Example The organization chart of a company can be represented using a rooted tree Each vertex corresponds to an employee with the root representing the chief executive of cer There is an edge between two vertices if one of the corresponding employees is the direct supervisor of the other The leaf vertices correspond to the lowest level employees who do not supervise anyone D In many applications in computer science objects have a hierarchical relationship in which each object is directly related to no more than two objects that are lower in the hierarchy For instance an object can correspond to a decision in which one of two options must be chosen and each of the lower objects represents the consequence of choosing one option This leads to the following de nition De nition Extended Binary Trees An extended binary tree is a graph that is de ned recur sively by 0 Basis Step The empty set is an extended binary tree A single vertex is also an extended binary tree and that vertex is called the root of the tree o Recursive Step If T1 and T2 are extended binary trees then the graph consisting of T1 and T2 a vertex x that is not in T1 or T2 and edges between T and the roots of T1 and T2 when these trees are nonempty is an extended binary tree which we denote by T1 T2 The vertex x is the root of T1 T2 The tree T1 is called the left subtree of T1 T2 and the tree T2 is called the right subtree of T1 T2 Example One computer game that has been popular for over twenty years is the game of Ani mals77 In this game you think of an animal and the computer tries to guess what the animal is using a series of questions whose answers are yes or no Each answer you provide tells the computer what question to ask next in order to identify the animal The questions are represented using an extended binary tree In this tree each vertex corre sponds to a question A yes answer to a question leads to the question at the root of the left subtree while a no answer leads to the question at the root of the right subtree A question at a leaf asks if the user is thinking of a speci c animal If not then the user adds to the binary tree by providing a question that can be used to distinguish between his or her guess and the computer s guess The more questions that are added the more likely the computer is to guess the animal that the user is thinking of D In some applications it is desirable to work with a binary tree that is balanced in some sense meaning that the tree has as few levels as possible in its hierarchy or that the average number of edges one must traverse to reach a leaf from the root is as small as possible This leads to the following more restrictive notion of a binary tree De nition Full Binary Trees A full binary tree is an extended binary tree that is nonempty and has the property that each vertex either has no svbtrees or it has both a left subtree and a right subtree A full binary tree can be de ned recursively by 0 Basis Step A single vertex is a full binary tree 0 Recursive Step If T1 and T2 are full binary trees then the graph consisting of T1 and T2 a vertex x that is not in T1 or T2 and edges between T and the roots of T1 and T2 is a full binary tree which we denote by T1 T2 The vertex x is the root of T1 T2 The tree T1 is called the left subtree of T1 T2 and the tree T2 is called the right subtree of T1 T2 Example A full binary tree is a useful data structure for implementing a binary search within a sorted list of numbers as discussed in Lecture 19 It is possible to construct a full binary tree in which each number in the list is assigned to a vertex and each vertex has the property that all numbers associated with the left subtree are less than the vertex s own number and all numbers associated with the right subtree are greater Then a binary search can proceed by comparing the number x for which we are searching to the number x at the root If they are equal we are done Otherwise we continue searching in the left subtree or the right subtree depending on whether r is greater or less than x D Structural Induction As previously mentioned recursion and induction share the common property that they relate larger instantiations of various concepts to smaller instantiations where these concepts can be predicates or de nitions of objects Because of this similarity it is natural to try to use induction to prove results pertaining to a recursively de ned structure This is equivalent to proving that a statement of the form Pn is true for each natural number n where n represents the number of applications of the rules of the recursive step in the de nition of the structure with n 0 corresponding to the basis step This use of induction is called structural induction The principle of structural induction states that a result holds for all elements that can be constructed using a recursive de nition if the following statements are true 0 Basis Step the result holds for all elements that are de ned in the basis step of the recursive de nition 0 Recursiue Step if the result holds for all elements used to construct new elements in the recursive step of the de nition then it holds for the new elements as well We now illustrate how this principle can be applied to prove results about recursively de ned structures such as binary trees The edges of a rooted tree form paths that originate from the root and terminate at each of the leaves The following recursive de nition is useful for measuring for a given full binary tree the maximum length of such a path De nition Height of Full Binary Tree The height of a full binary tree T denoted by hT is de ned recursiuely by 0 Basis Step IfT is a full binary tree consisting of a single uerteI then hT 0 o Recursive Step if T1 and T2 are full binary trees then hT1 T2 1 maxhT1 hT2 The following result illustrates how full binary trees are balanced that is its vertices are condensed into as few levels in the hierarchical structure of the tree as possible Theorem IfT is a full binary tree with n uertices then n m il Proof We prove this result using structural induction The basis step corresponds to a binary tree T consisting of a single vertex In this case n 1 and hT 0 so we have 1 711 7 Jim Lambers Math 6A Spring Quarter 200304 Lecture 25 Notes These notes correspond to Section 64 in the text Generating Functions In recent lectures we have learned how to evaluate recursively de ned functions more ef ciently by using various techniques to convert recursive de nitions to explicit ones These techniques however are somewhat limited in their applicability as we have only been able to consider speci c classes of recursive de nitions In this lecture and the next we will learn a more powerful approach to evaluating functions whose values are either de ned recursively or de ned to be solutions of counting problems In either case the original problem requires one to compute terms of a sequence ak We will accomplish this by working with a function Cz called a generating function that is de ned using the terms of the sequence as indicated in the following de nition De nition Generating Function Let a io be a sequence The generating function for the sequence ak denoted by Cm is 00 Cm Z akzk k0 Example Recall from Lecture 20 that if lt 1 then 00 1 E kxkil 7 2 k1 1 m By shifting the index of summation by 1 we can rewrite this equation as 00 1 Eng 1M 2 k0 1 7 m It follows that Cm 117z2 is the generating function for the sequence 01152 where ak k1 for each nonnegative integer k D Example Consider the function 1 m lmllt1 Using the formula 1 0 k Zr MltL k0 lir we can see that Cm can be written as By rewriting the sum as m0m24 M8 8 w H o m00m1z20z3m40m5 CO 2am k0 where 7 1 if k is even at 0 if k is odd we have obtained the sequence ak whose generating function is equal to D The way in which a generating function Cm can be used to compute terms of the underlying sequence ak whose terms are the coef cients of Cz varies from problem to problem but in general one proceeds to using knowledge about the terms of ak such as a recursive de nition to obtain a formula for This formula can then be used to obtain the terms of the sequence Useful Facts about Power Series Any series whose terms have the form akmk where k is a nonnegative integer and ak is a constant for each k is called a power series By de nition a generating function has a power series repre sentation In order to be able to compute the terms of a sequence from its generating function one must be able to obtain a power series representation from as wide a variety of functions as possible We now present some de nitions and results that aid in this task The following result is useful for obtaining sequences from generating functions that are built from other generating functions whose sequences are known Theorem Let and 9m be generating functions for the sequences ak and bk respectively that is 00 00 M 2am gltzgt 2w k0 k0 Then 00 00 k fltzgtgltzgt72ltakbkgtzk and mm Zajbk7j zk ko k0 j0 That is 9a is the generating function for the sequence ak bk and is the generating function for the sequence ck where ck 20 ajbk 39 for each h E N Example Let x 117 z2 and 9a 117 m where lt 1 Then7 from the formulas 1 1 k k 7 7 72k17 17m kio 17m2 kio we see that x is the generating function for the sequence at7 where ak k 1 for each h E N and 9a is the generating function for the sequence bk7 where bk 1 for all k E N By the preceding theorem7 we have j11mk ma mb g a H M w 0 A Qt H V s R A gt A H PT to V w R H mm EM8 EM8 EM8 i V H DXV 8 Z Ck 2 km k0 We conclude that 117 z3 is the generating function for the sequence ck where ck Ck 27 k for each h E N D Suppose that n is a nonnegative integer By the Binomial Theorem7 the sequence MEL Whose terms are given by Cn7 k if k g n ak l 0 if k gt n Jim Lambers Math 6A Spring Quarter 200304 Lecture 23 Notes These notes correspond to Section 62 in the text Solving Recurrence Relations In the previous lecture we learned how to model a counting problem using a recurrence relation which is an equation that relates each term in a sequence to previous terms In this lecture we will learn how to solve certain types of recurrence relations in order to obtain an explicit formula for each term that is independent of the other terms Solving Linear Homogeneous Recurrence Relations with Constant Coe icients A recurrence relation is said to be linear if each term in the equation that depends on a term of the sequence that it describes is a multiple of that term The quantity multiplying the term is a coe cient in this lecture we will consider only recurrence relations with constant coefficients If every term in the recurrence relation is a multiple of a term then we also say that the recurrence relation is homogeneous In summary a linear homogeneous recurrence relation with constant coef cients can be written in the form an Giana 6272 Ckanik The number k is called the degree of the recurrence relation provided that the coef cient ck is nonzero We will now learn how to solve recurrence relations of this form beginning with those of degree 2 Theorem Let an Giana 6272 be a linear homogeneous recurrence relation of degree 2 with constant coe icients If the polynomial r2 7 clr 7 62 has two distinct roots T1 and r2 then a sequence an is a solution of the recurrence relation if and only if an 041 agrg where 041 and 042 are constants Proof First we must show that if an 0417 0427 for each integer n then the sequence an satis es the recurrence relation We have n71 n71 n72 n72 Clanil l CZaniZ 61041T1 04er 62041T1 042T2 air 201ri 02 0427 37201T2 02 n72 2 n 72 2 alrl T1042T2 72 0417 0427 an Now we must show the converse if a sequence an satis es the recurrence relation then for each nonnegative integer 71 an 0417 agrg for some choice of the constants 041 and 042 We will prove this t using induction The basis step corresponds to n 0 and n 1 We will use a constructive existence proof that is we will nd constants 041 and 042 such that an 0417 04ng for these values of 71 Setting n 0 and n 1 in this equation we obtain the system of equations 041042 a0 041T104272 a1 Because 71 7 r2 this system has the unique solution 7200 7 a1 a1 TWO 7 0 2 7 041 72 7 Tl 72 7 Tl as can be determined by substituting a0 7 041 for 042 in the second equation For the inductive step we assume that n71 n n n71 an 04171 042727 anil 041 04275 7 where n 2 2 and show that an 0417 0427 Since an satis es the recurrence relation we have an1 Clan CZanil 71 71 c alr 04273 02 0417 0427 l 71 71 04161T1L 62 l 042clrg 327 041T7101T1 02 azrgillc z 02 041711klr agrgilrg 0417 0427 and the proof is complete D Example Consider the recurrence relation satis ed by the Fibonacci numbers an anil 04127 with a0 0 and a1 1 Using the preceding theorem we can solve this recurrence relation by computing the roots of the quadratic equation r2 7 r 7 1 0 Recall that the solutions of a quadratic equation of the form azz bx c 0 are given by the quadratic formula 7 7b i V192 7 4ac 7 T39 Using this formula we obtain 1i 1124111i5 W 7 2 7 Since these roots are distinct it follows that the solution has the form 1 x3 n 17 x3 n an 041 042 7 2 2 where 041 and 042 are constants determined by the initial conditions a0 0 and a1 1 From the proof of the preceding theorem we have PTVEOA 7 71 7 71 17 1 5 7 17 5717 5 7 72 2 2 2 2 041 1 V37 171 950 1 7 1 175 157725 739 TWJTW Tr 5 711 Sn117 3n THE 2 7ET The preceding theorem required that the two roots of r2 7 clr 7 02 be distinct We now consider the case of two identical roots 042 We conclude that Theorem Let an Clan71 6272 be a linear homogeneous recurrence relation of degree 2 with constant coe icients If the polynomial r2 7 clr 7 62 has a double root n then a sequence an is a solution of the recurrence relation if and only if TI TI an 04171 0427quot 17 where 041 and 042 are constants Proof First we must show that if an 0417 042717 for each integer n then the sequence an satis es the recurrence relation Because 71 is a double root the polynomial r2 7 61 7 62 has the factorization r 7 r12 It follows that 7276177627 272nrr which yields 61 271 62 77 It follows that 61an1 62an2 61041771L 1 a2n 7 1r71 6204171kz a2n 7 2r72 alr 261n 62 042T72Cl n 71 62n 7 2 041711kzr a2r 2n61n 62 7 ClTl 7 262 0417 a2r 2nr 7 ClTl 7 262 0417 042717 7 a2r 261n 262 0417 042717 7 a2r 22nn 27r 0417 042717 7 a2r 22r 7 27 0417 042717 an Now we must show the converse if a sequence an satis es the recurrence relation then for each nonnegative integer 71 an 0417 042717612 for some choice of the constants 041 and 042 We will prove this t using induction The basis step corresponds to n 0 and n 1 We will use a constructive existence proof that is we will nd constants 041 and 042 such that an 0417 042717 for these values of 71 Setting n 0 and n 1 in this equation we obtain the system of equations 041 a0 mm 04271 ai This system has the unique solution a1 7100 041 107 042 7 T1 as can be determined by substituting 041 am in the second equation For the inductive step we assume that 71 71 analra2nr an1alr 0420171 where n 2 2 and show that an1 our a2n 1r1 Since an satis es the recurrence relation we have an clan cganil cl 0417 agnrm 62041T1L71 a2n 7 Dril l 041clr 62T71 042clnr 6271 7 Dril l Infillcm 02 042T71n01r2 02 7 02 041T71T agilil 717 7 041T71T agr71n Dr 041T71T a2n 71 0417 a2n 1r1 and the proof is complete D Example Consider the recurrence relation an 2an71 7 an727 with initial conditions a0 3 and a1 71 We will solve this relation by computing the roots of the equation 72 2T 7 1 Since the polynomial r2 7 2r 1 can be factored into r 7 12 it follows that the equation has a double root of 1 Therefore by the preceding theorem the recurrence relation has a solution of the form an 0411 042711 041 04271 where 041 and 042 are constants From the proof of the preceding theorem we obtain a1a03 a2 m717374 We conclude that the solution of the recurrence relation is an 3 7 4n D The equation 72 clr r2 is called the characteristic equation of the recurrence relation an clan1 czanq In general the characteristic equation of the recurrence relation k an E ckanij 73971 can be obtained by substituting an r into the recurrence relation7 which yields k r chrn j1 and then dividing by rn k to obtain the characteristic equation k rn k Z ckrk j 71 We will now use this characteristic equation to generalize the preceding theorems to recurrence relations of higher degree Theorem Let k an Z Cjanij j1 be a linear homogeneous recurrence relation of degree k with constant coe icients If the character istic equation k k I kij r 7 2 car j1 has k distinct roots r17r2 7rk then a sequence an is a solution of the recurrence relation if and only if h an Zajrgl j1 where 04739 is a constant forj 127 k Proof First7 we must show that if an 21 air for each integer n7 then the sequence an satis es the recurrence relation We have k k k c 39a 39 i C39 04 39rnij 7 n77 J l 139 71 11 11 k k I 2 04 Z ery i1 j1 k k I Z airyik 2 gig i1 j1 k Zairyikrf i1 k 2w i1 an Now we must show the converse if a sequence an satis es the recurrence relation then for each nonnegative integer 71 an 21 0471 for some choice of the constants 041 042 Ozk We will prove this using The basis step corresponds to n O 1 k 7 1 We will use a constructive existence proof that is we will nd constants 041042 Ozk such that an 21047397 for these values of 71 Setting n O 1 k 1 in this equation we obtain a system of k equations for the k unknowns 041 042 Ozk Because the roots r1 r2 rk are all distinct it is known from linear algebra that this system has a unique solution that can be obtained using Gaussian elimination For the inductive step we assume that t t induction k a Zajr 2 O1k7 1 j1 where n 2 k and show that k 1 an 204739 er j1 Since an satis es the recurrence relation we have k an1 Cjan17j 71 k k I Z 0739 Z air l j1 i1 k k I Z a Z errrl 3971 j1 k k I Z airyik 2 Cij7 i1 j1 k Z airyik rg i1 7 k 04er i1 and the proof is complete D Finally we consider the case where the characteristic equation for a recurrence relation of degree k has multiple roots Theorem Let k an Z Cjanij j1 be a linear homogeneous recurrence relation of degree k with constant coe icients If the polynomial k k I kij r 7 07 j1 has t distinct roots r1r2rt with multiplicities m1m2mt then a sequence an is a solution of the recurrence relation if and only if t mjil an E E Ozjj n T j1 i0 where 04739 is a constantforj12k andi01mj71 Linear Nonhomogeneous Recurrence Relations with Constant Coe icients We now consider the solution of linear recurrence relations with constant coefficients that are nonhomogeneous These recurrence relations include terms that do not depend on the terms in the sequence that they describe As such they have the form h an Z ejan 39 Fn j1 where is an arbitrary function of n We will see that recurrence relations of this form can be solved in a fairly straightforward manner for certain choices of the function First however it should be noted that the solution to a nonhomogeneous recurrence relation is not unique There are actually in nitely many solutions but all of them can be described in terms of the solutions of the recurrence relation that is obtained by removing the term The resulting homogeneous recurrence relation h an Z ejanij j1 8 is called the associated homogeneous recurrence relation We now state the precise relationship between solutions of this recurrence relation and the corresponding nonhomogeneous recurrence relation Theorem Let k an ch39anij j1 be a linear homogeneous recurrence relation of degree k with constant coe cients If 157 is a particular solution of the recurrence relation then euery solution is of the form 1217 1 where 1 is a solution of the associated homogeneous recurrence relation h an E cganij 11 Proof Suppose that bn is a solution of the nonhomogeneous recurrence relation By subtracting the equation bn Cjbnij Mw H J from the equation k at chaiflj M j1 we obtain the equation at 7 I Z waif 7 bwl M 7 M j1 which can be rewritten as k h as mtg j1 where we de ne agh a 7 I It follows that allm is a solution of the associated homogeneous recurrence relation By the de nition of ago7 we have bn a all so the solution bn has the desired form D Now that we know the form of all solutions of a linear nonhomogeneous recurrence relation with constant coefficients7 it remains to nd a particular solution The following result provides a method for accomplishing this task for certain choices of the function Jim Lambers Math 6A Spring Quarter 200304 Lecture 18 Examples These examples correspond to Sections 15 and 33 in the text Example Let n be a two digit positive integer that is7 let n be an integer satisfying 1 g n g 99 Prove that n is divisible by 3 if and only if the sum of its digits is divisible by 3 Solution Since we are trying to prove a biconditional statement of the form p lt gt q7 we must use a proof by equivalence We complete the proof in two steps that correspond to proving that p a q and q gt p o p a q we prove that if the sum of the digits of n is divisible by 37 then n is divisible by 3 We write n 10p q7 where p is the tens digit and q is the ones digit Then our hypothesis is equivalent to the statement that p q 3k for some integer k It follows that n 10pq 1019 3kip 9p3k 33pk7 so n must be divisible by 3 o q a p we prove that if n is divisible by 37 then the sum of its digits is divisible by 3 Our hypothesis is equivalent to the statement that n 3k for some integer k As in the previous step7 we write n 10p q It follows that 10p q 3k7 and therefore pqp3k1019 3k9P3k3P7 so the sum of the digits must be divisible by 3 Note that not all equivalence proofs necessarily proceed in this manner An alternative approach is to prove that p a q and pp a g which is the contrapositive of q a p D Example Show that the statements p a q and q a p are not logically equivalent Solution This can be accomplished by nding a counterexample to the claim that p a q and q a p always have the same truth value It is sufficient to nd one combination of truth values for p and q for which p a q and q a p have different truth values it is not necessary to check all possible truth values Suppose that p is false and q is true Then p a q is true7 because it is equivalent to ppV q On the other hand7 q a p is false7 because it is equivalent to pp Vp Because p a q and q a p do not have the same truth value for all possible combinations of truth values ofp and q7 we can conclude that they are not logically equivalent D Example We will prove that a postage stamp worth n cents where n 2 20 can be purchased using a combination of 5 cent stamps and 6 cent stamps Solution We will prove this statement using mathematical induction in two different ways The rst uses standard mathematical induction while the second uses strong induction which is also known as the second principle of mathematical induction Let Pn be the statement a postage stamp worth n cents where n 2 20 can be purchased using a combination of 5 cent stamps and 6 cent stamps77 For the rst approach the basis step involves showing that P20 is true It is true because we can simply use four 5 cent stamps to buy a 20 cent stamp For the inductive step we assume that Pn is true for an arbitrary integer n 2 20 and show that it must follow that Pn 1 is true Since Pn is true we can write n 5j 6k where j and k are nonnegative integers with j being the number of 5 cent stamps and k being the number of 6 cent stamps needed to buy an n cent stamp Suppose that j gt O that is at least one 5 cent stamp is used to buy the n cent stamp Then we can trade a 5 cent stamp for a 6 cent stamp and buy an n 1 cent stamp That is n15j6k15j7156k15j716k1 Now suppose that j 0 so no 5 cent stamps are used to buy the n cent stamp This implies that n is a multiple of 6 that is n 6k for some nonnegative integer k However because n 2 20 we must have k 2 4 Therefore we can exchange four 6 cent stamps worth 24 cents in total for ve 5 cent stamps which are worth 25 cents in total In other words n16k16k746416k74256k7455 We have shown that if an n cent stamp can be purchased using 5 cent stamps and 6 cent stamps where n 2 20 then an n 1 cent stamp can be purchased using such a combination as well In other words we have shown that Pn implies Pn 1 By the principle of mathematical induction the proof is complete Pn is true for all n 2 20 Now we prove the statement using strong induction In this case our basis step involves showing not just P20 but P20 A P21 A P22 A P23 A P24 We know that P20 is true since we can buy a 20 cent stamp using four 5 cent stamps In addition we can buy a 21 cent stamp using three 5 cent stamps and one 6 cent stamp a 22 cent stamp using two stamps of each kind a 23 cent stamp using one 5 cent stamp and three 6 cent stamps and a 24 cent stamp using four 6 cent stamps This completes the basis step For the inductive step we assume that Pk is true for each integer k satisfying 20 g k g n where n 2 24 is an arbitrary positive integer and we must now show that Pn 1 must be true as a result Because n 2 24 it follows that n 7 4 2 20 By our assumptions since 20 g n 7 4 g n an n 7 4 cent stamp can be purchased using a combination of 5 cent stamps and 6 cent stamps If we add another 5 cent stamp then we can purchase a stamp that is worth n 7 4 5 n 1 Jim Lambers Math 6A Spring Quarter 200304 Lecture 17 Examples These examples correspond to Sections 53 and 15 in the text Example Let S be the sample space of all possible sequences of n independent Bernoulli trials with probability of success p and let X S a R be a random variable that counts the number of successes in each sequence What is VX Solution For each i 1 2 n we de ne the random variable X S a R as follows for each s E S Xis 1 if the ith trial in s succeeds and Xis 0 otherwise Then it follows that X X1 1 X2 1 X since a 1 is contributed to the sum whenever a trial succeeds and Xs is the number of successes in 3 Our goal is to compute VX by computing VXi for each i between 1 and n and adding these variances However the relation is only valid if EXEXj EXXj for ij 1 n with i 7 j To see why examine the proof in the Lecture 16 notes that VX Y VX VY if X and Y are independent random variables We now verify that EXEXj EXXj ifi 7 j Since X can only assume the values 0 and 1 we have EXi Z T1909 7 TEXAS 1p01p p In addition because Xins 1 only when Xis 1 and Xjs 1 we have EXX Z rpXinr reXinS 1p201p2 292 Therefore EXEXj p p p2 EXXj It follows that VX VX1 VX2 1 VXn Jim Lambers Math 6A Spring Quarter 200304 Lecture 26 Notes These notes correspond to Section 64 in the text Generating Functions cont d In the previous lecture we learned how sequences could be represented using generating functions We now learn how to use generating functions to compute an individual terms of sequence that represents the solution to a counting problem or all of the terms of a sequence that is described by a recurrence relation Counting Problems and Generating Functions Generating functions are very useful for counting problems in which it is necessary to count the number of ways to choose a collection of nonnegative integers subject to given constraints such that the sum of the integers in the collection is equal to some given value r The solution to such a counting problem is given by the coefficient of K in the power series expansion of a generating function Cz where Cm is determined by the constraints of the prob lem Once the correct generating function is found then one can use formulas for the power series coefficients of known generating functions to compute the coefficient of In the following examples we show how the appropriate generating function can be obtained from the speci cs of the given counting problem Example Consider the problem of choosing the number of ways to add 3 nonnegative integers so that their sum is equal to 10 This number is equal to the coefficient of 10 in the power series expansion of the generating function Czm0z1m2m3x43 Each factor of m0 1 2 corresponds to the choice of a single nonnegative integer and within each of these factors each term 7 corresponds to a choice of j The reason that the number of ways to choose three integers that sum to 10 is equal to the coefficient of 10 in the power series expansion of Cm is that Cm can be written as a sum of terms of the form zmzmmm zmim m where mm for j 123 is a term in the jth factor x0 m1 m2 of By combining all of the terms of this form for which 711 712 713 10 we obtain a term of the form alozlo in the power series expansion of The coefficient am is the number of terms of the form mmzmmm that have been combined or equivalently the number of ways to add three nonnegative integers and obtain a sum of 10 If we assume that lt 1 then we have 1 17m7 CO 012Zx n0 which yields 1 1795 Using the formulas for the coefficients of known generating functions we have Cm 1 CO C3n713zn new It follows that the coefficient of 10 which is the number of ways to add 3 nonnegative integers to obtain a sum of 10 is 12 10 11 12 C3 10713 012 3 220 lt gt lt gt 39 6 D Remark It is useful to note that Cm is a product of three functions G1z G2z and G3z where each function corresponds to the choice of a single nonnegative integer of the three that must be chosen in sequence Furthermore each function is a sum of terms where each term 7 corresponds to the choice of j The structure of Cm corresponds closely to the usage of the Product Rule and the Sum Rule to count the number of ways to accomplish a given task In this case we must perform a sequence of three tasks where each task consists of choosing an integer but each of these tasks can be accomplished by performing only one of the tasks of choosing O choosing 1 choosing 2 and so on The number of ways to perform a sequence of tasks is counted using the Product Rule and the number of ways to perform a single task in one of many ways is counted using the Sum Rule This is re ected in the structure of the generating function which is a product of sums corresponding to the completion of a sequence of three tasks where each task can be completed in in nitely many ways D Example Suppose that we must count the number of ways to add three nonnegative integers and obtain a sum of 10 as in the preVious example except that the integers are constrained That is we must nd three integers 51 52 and 53 such that 51 52 53 10 and 0 g 51 g 5 3 g 52 g 7 and 7 g 53 g 9 These constraints limit the terms that appear in the generating function As before Cm is a product of three factors corresponding to the choices of 51 52 and 63 However each factor can only include terms corresponding to the integers that can be chosen Speci cally we have Cm 1mz2x3m4z5m3m4x5m6z7m7m8x9 Computing the expansion of Cz we nd that the coef cient of 10 is 1 This means that there is only one way to choose three nonnegative integers subject to the given constraints and obtain a sum of 10 The only way is to choose 51 0 52 3 and 53 7 D Example Suppose that we need to count the number of ways to choose 1 5 10 or 20 bills in order to obtain a sum of 25 If we stipulate that the order in which the bills are chosen is relevant then the generating function for choosing k bills is Gkm m1 5 10 20k since the task of choosing k bills is accomplished by performing a sequence of k tasks where each task involves choosing one bill of any type Since we can choose any number of bills to obtain a sum of 25 it follows that the generating function for this task is 1 5 10 20k zm m m 7 1imim5710720 M8 C35 2 am k0 w H 0 Using a computer algebra system such as Maple we can compute the coef cient of 25 of Cz which is 923 This is the number of ways to obtain a sum of 25 from bills of the given denomina tions D Example We repeat the previous example in which we are counting the number of ways to choose 1 5 10 or 20 bills in order to obtain a sum of 25 except that in this case the order is irrelevant It follows that the task of choosing bills consists of a sequence of four tasks The rst task involves choosing a number of 1 bills the second involves choosing a number of 5 bills the third involves choosing a number of 10 bills and the fourth taks involves choosing a number of 20 Since we are not concerned with the order in which the bills are chosen only the number of bills of each type is relevant It follows that the generating function for this counting problem is Cz 1zz21z5z101z10z201z20z40 1 Each factor of Cm corresponds to choosing a number of bills of one denomination and the sum within each factor re ects the fact that we can choose any number of bills of each denomination Using Maple we nd that the number of ways to obtain a sum of 25 using these bills is 14 D Example We now show how generating functions can be used to compute the number of r combinations of a set containing 71 elements where repetition is allowed To construct the generat ing function for this problem we note that choosing r elements from the set can be accomplished by performing a sequence of 71 tasks In the ith task for i 1 2 n we determine how many times the ith element can appear in the combination Because we can choose to include the ith element 0 times 1 time 2 times or any other number of times it follows that the generating function Cm is given by Cm 1xm2z3n 00 n E j0 1 l a V 3 AAA HHH l AR V l 3 Vi HAA l l 3 w3 w3 VV T T H R V V F w R R H H M8 n18 n18 n18 n18 n18 n18 ElH E 3 g s ET L a We conclude that the number of r combinations is equal to the number of ways to add 71 nonnegative integers to obtain a sum of r where each integer corresponds to the number of each element that is included in the combination The number of such combinations is therefore equal to the coefficient of z in the power series expansion of Cz which is Cn r 7 1 r B As can be seen from the preceding examples the generating function can be constructed using the interpretations of the Product Rule and the Sum Rule as techniques for counting the number of ways to accomplish tasks A sequence of numbers to be chosen corresponds to a product of gen erating functions that represent the individual choices to be made A choice of ways to accomplish a task corresponds to a sum of the generating functions that represent each option Using Generating Functions to Solve Recurrence Relations Since the solution to a recurrence relation is a sequence and generating functions can be used to compute the terms of a sequence it is natural to consider whether generating functions are useful for solVing recurrence relations This is in fact the case as we illustrate in the following examples Example We will use a generating function to solve the recurrence relation an 4an71 a0 2 We begin by multiplying both sides of the recurrence relation by z and summing from n 1 to in nity to obtain the equation In the summation on the right side we can shift the indices down by 1 to obtain 00 00 2 0mm 4 E anmn n1 n0 Factoring z out of this summation yields 0 0 2 0mm 4m 2 anxn n1 n0 We de ne Cm to be the generating function for the sequence an Then since G i anxn n0 it follows from our preVious work that Cx 7 aomo 4zGx From the initial condition we obtain the equation Cx 7 2 4xGm which we can solve for Cm to obtain 2 G 3 17 4m Using the summation formula 1 00 n r Z 1777 n0 with r 4m we obtain C95 2174M 22m Q2 4 from which we conclude that an 2 4 for each nonnegative integer n D Example The technique from the preceding example can also be applied to nonhomogeneous recurrence relations We illustrate this by using a generating function to solve an 4an1 3 7 a0 71 Proceeding as before7 we multiply both sides of the recurrence relation by z and sum from n 1 to in nity to obtain 00 00 00 2 0mm 4 Z an1z Z 37 n1 n1 n1 If we de ne Cm to be the generating function for the sequence an7 it follows from the preceding equation that CO Cx 2 0mm n0 CO aomo 2 0mm n1 CO CO 71 4 Zan1m 237 1 n1 CO CO 71 4 Z anmn 7 3m0 0 n0 1 714mZanmnmil n0 72 4zGx 276m 1 7173351 173z4G 6m71 1 3m 4xGm 1 173m It follows that 6m 7 1 17 3m17 4x We can compute the coefficients of the power series of Cz7 which are the terms of the sequence an7 by computing the partial fraction decomposition of This decomposition has the form Cx 63571 7 A B 173174m7173m 174m7 where A and B are constants Multiplying both sides of this equation by the denominator yields the equation 6x71 A174m B17 3x Since this equation must hold for all m we can substitute z 13 and z 14 to obtain the equations 61371 A17 437 61471 B17 347 which yield A 73 and B 2 Using the formula for the sum of a geometric series7 we obtain 73 2 C95 17 3m 17 4m 00 00 73 2m 2 24z n0 n0 0 Z733n24 z n0 and conclude that an733 24 for each nonnegative integer n D Example We show how generating functions can be used to obtain an explicit de nition of the Fibonacci sequence de ned by the recurrence relation fnfn71fn727 f007 f1 As in the previous examples we multiply both sides of the recurrence relation by x but this time we sum from n 2 to in nity since the recurrence relation has degree 2 This yields 00 co 00 Z fnn Z fn71n l 2 fn72n n2 n2 n2 Shifting indices in the sums on the right side we obtain 00 co co 1 2 Z fnmn Z fnn l 2 fnn 7 n2 n1 n0 which upon factoring out powers of z in these sums becomes 00 00 00 Z fna 95 Z fnm 902 Z fnz n2 n1 n0 It follows that if Cm is the generating function for the Fibonacci sequence we have Cx 7 flm 7 f0 7 f0 z2Gx Using the initial conditions we can simplify this equation to obtain Cm 7 m mGm z2Gx which yields the generating function 1 G a 1 7 m 7 m2 We must now compute the coefficients of the power series of Cz which are the terms of the Fibonacci sequence We use the fact that Cm has a partial fraction decomposition of the form m A B 17x7m2 771 7727 where A and B are constants and T1 and r2 are the roots of the polynomial 1 7 z 7 m2 By the quadratic formula these roots are 11 471 7 4mm 71 i 3 gt2 271 2 The constants A and B can be computed by multiplying both sides of the partial fraction decom position by 1 7 z 7 m2 which yields the new equation m Ax 7 72 Bx 7 T1 Since this relation must hold for all x we can substitute z T1 and z r2 to obtain Tl 72 7 B 7617762 7627761 If we let 71 be the root corresponding to the choice of the sign7 then we have 1 G m limimz 1 111 2 T1 7 WW 7 71 T2 7 NW 7 T2 1 1 71772lt7gt T27T1lt71gt 1 1 T2 7T1lt 7 T1 7 T2 7 1 1 n 1 1 m m nimgr 717727 3 Because 1 5 17 5 2 5 4211 37 2 2 2 and if 2 if 2 1 577217S7175 r1 1 5 1x31 3 74 2 7 7 2 if 2 1 5 721 371 5 r27 17 5 17 31 3 i4 2 7 we conclude that 1 1 1 1 Gm 7 mn zn nimgr 717727 3 1 17 5 1 1 5 Z W nZ f n n0 2 0 2 5 n0 2 V5 2 and see that the coef cients agree with the explicit de nition of the Fibonacci numbers obtained in Lecture 23 D Jim Lambers Math 6A Spring Quarter 200304 Lecture 24 Notes These notes correspond to Section 63 in the text Divideand Conquer Algorithms and Recurrence Relations In the previous lectures we have studied recurrence relations in which a term an of a sequence is determined by preceding terms an1 an ank where k is the degree of the recurrence relation These recurrence relations arise from problems in which the solution for an input of size n where the notion of size of the input depends on the problem can be obtained from solutions of slightly smaller instances of the same problem such as those of size n 7 1 n 7 2 and so on However in many cases a problem with input of size n can be solved by reducing the problem to a problems with input of size nb for some I gt 1 and then constructing the solution of the original problem from the a solutions that are obtained This approach to problem solving is known as diuide and conquer The number of operations performed to solve a problem in this manner which we denote by fn satis es a recurrence relation of the form 1 Mn19H 9007 where gn denotes the number of operations needed to construct the solution of the original problem of size n from the a solutions of problems of size nb The following theorem provides essential insight into the complexity of certain classes of divide and conquer algorithms We use the big Oh notation to measure complexity A function fn is said to be Ogn if there exists a constant c such that fn cgn for all n 2 n0 for some integer no Theorem Master Theorem Let f be an increasing function that satis es the recurrence relation 1 01 aJ Wb m h whenever n bk for some positive integer k a Z l b is an integer greater than 1 c gt 0 and d 2 0 Then 0nd if a lt bd fn 0ndlogn if a bd 0n10gb if a gt bd Proof For simplicity7 we assume that f1 c this assumption will not affect the growth of 1 that we are trying to measure We then have 1 a nb 0nd ala nbz CWWl 0nd a2fnb2 o unbd 1 6nd a2afnb3 Cnb2d acnbd 6nd a3fnb3 2L2 3nI2d o unbd 1 6nd 771 aj nbj cndzai1bid i 0 1 mew120 CHEWW i0 logbnil alogw1md Z abdy39 i0 w 71 alogb c 1 6nd abdy l H o kil alogb ncndbdk End abdi i0 k 6nd 2abdi i0 This expression for fn can be proven more rigorously using mathematical induction7 which we do not do here The sum is a geometric series with initial term and and common ratio abd We consider three cases 0 abd lt 1 The sum of the geometric series is bounded by 11 7 Lbd7 and therefore fn 0nd o abd 1 The sum of the geometric series is fn cndk endlogbn 0ndlogn o abd gt1 We have dltabdgtk1 e 1 fl Cquot W Jim Lambers Math 6A Spring Quarter 200304 Lecture 17 Notes These notes correspond to Section 15 in the text Methods of Proof In previous lectures we learned how to construct propositions and determine their truth values In this lecture we begin to show how propositions can be used to construct mathematical arguments which are sequences of true propositions ln mathematics such arguments are used to establish the truth of statements called theorems which are also referred to as propositions or results An argument that is used to prove that a theorem is true is called a proof Theorems are logical consequences of previously proved theorems hypotheses and axioms which are assumptions about underlying mathematical structures that are accepted as true without proof As such it can be said that theorems provide us with a means of systematically obtaining new interpretations of previously established facts These new interpretations which are difficult for us to obtain by other means can then be used to provide valuable insight into the nature of the mathematical entities they discuss Mathematical arguments also play an essential role in computer science In this context one can prove for example a theorem that states that a given computer program is correct or that a system is secure or that a set of system speci cations is consistent In later lectures we will also see how theorems can even be used to design algorithms to be used in computer programs Rules of Inference A rule of inference is a tautology of the form VquRp q a Sp q where the universe of discourse for p and q is the set of all propositions and Rp q and Sp q are predicates that are compound propositions built from the propositions p and q The proposition Rpq is a conjunction of one or more propositions that are called hypotheses and the proposition Sp q is called a conclusion Such rules serve as some of the building blocks77 of proofs since they can be used to show that a conclusion is a logical consequence of a set of hypotheses A conclusion can then serve as a hypothesis from which additional conclusions can be inferred This process of repeated inference can continue until the underlying theorem is proved The following table lists the most common rules of inference When describing these rules we dispense with the quanti ers for the sake of brevity and use only the underlying predicate The predicate of a rule of inference becomes a tautology when propositions are substituted for its variables that represent the hypotheses and the conclusion This predicate is also known as an argument form A A VTgt Rules of inference are applied by substituting speci c propositions for the hypotheses and the conclusion into the rule s argument form If the hypotheses are true then because a rule of inference is a tautology it follows from the de nition of the implication that the conclusion must be true In this case we say that the resulting argument that the conclusion follows from the hypotheses is a valid argument Example Let p be the statement It is not raining and let q be the statement We may go outside Suppose that p is true and that the statement If it is not raining we may go outside is also true Then by the modus ponens rule of inference we can conclude that q is true that is we may go outside D Example Let p be the statement The rain is freezing q be the statement The roads will be icy and r be the statement The roads will be slippery Suppose that the following statement is true If the rain is freezing the roads will be icy and if the rain is not freezing the roads will be slippery Then by the resolution rule of inference we can conclude that q V r is true that is the roads will either be icy or slippery and therefore it is best to stay home D Fallacies A fallacy is a contingency that is used as if it were the argument form of a rule of inference typically because it resembles such a rule However because it is a contingency rather than a tautology a fallacy can cause an argument to be invalid The following fallacies are particularly common 0 The proposition p a q Aq a p bears a close resemblance to either modus ponens or modus tollens However it is a contingency since it is false whenever p is false and q is true This fallacy is known as the fallacy of a rmlng the conclusion It is mistakenly used to prove that because a conclusion is true the corresponding hypothesis must also be true which is not always the case o The proposition p a q A pp a g is false whenever q is true and p is false so it is a contingency Due to its close resemblance to modus ponens and modus tollens it is often mistakenly used in arguments to prove that if a hypothesis is false then the corresponding conclusion must also be false This fallacy is called the fallacy of denying the hypothesis 0 The proposition Lp lt gt q a q is false whenever p is false and q is false This fallacy known as begging the question or circular reasoning occurs when the conclusion is mistakenly assumed to be true in the process of trying to prove that the conclusion is true We now illustrate some of these fallacies in the following examples Example In calculus it is known that if a function is differentiable then it is continuous Often however calculus students with regard to this statement affirm the conclusion and claim that a continuous function is automatically differentiable which is not necessarily the case B Example The following is a true story a customer at a gas station asked the clerk why the station did not accept credit cards The clerk replied that it was because they did not have a machine for processing credit card transactions When asked why they do not have such a machine the clerk responded that it was because they don t accept credit cards This is an example of circular reasoning which as this example shows can be a source of considerable frustration for its victims D Rules of Inference for Quanti ed Statements Although we have de ned rules of inference to be tautologies obtained by universal quanti ca tion the hypotheses and conclusion of a rule of inference can contain quanti ers themselves The following table lists common rules of inference that feature quanti ers A an gt some Example The famous syllogism All men are mortal Socrates is a man Therefore Socrates is mortal is an example of universal instantiation where Pm is the predicate m is mortal the universe of discourse for z is all men and 0 represents Socrates By this rule of inference VzPm gt Pc D Methods of Proving Theorems We now describe various techniques for using rules of inference to prove theorems These techniques provide much exibility in constructing eqnence of t t t that t t show that the desired conclusion is a logical consequence of the original assumptions 0 A direct proofin an argument in which the implication p a q is proven to be true by assuming that p is true and showing that as a consequence q must be true This rules out the possibility that q is false when p is true and therefore the entire implication must be true 0 An indirect proof is used to prove that an implication p a q is true by proving using a direct proof that the contrapositive q a p is true In other words we assume that q is false and show that p must also be false This approach is valid because any implication is logically equivalent to its contrapositive o A uacuous proof is used to show that p a q is true by showing that p is false in which case the truth value of q is irrelevant Similarly a trivial proofis used to show that p a q is true by showing that q is true in which case the truth value of p is irrelevant Both methods of proof use the Addition Rule of inference o A proof by contradiction is used to show that a proposition p is true by nding a contradiction q such that p a q is true Because q is always false the only way this can be the case is if p is false meaning that P must be true 0 A proof of equivalence is used to show that two propositions p and q are equivalent by showing that the biconditional p lt gt q is true This is typically accomplished by showing that p a q and q gt p We now illustrate some of these methods in the following examples Example We use a direct proof to show that z2 gt 0 if z is any nonzero real number We rst assume that z gt O Multiplying both sides of this inequality by z yields by the laws of algebra the inequality z2 gt O which is the desired conclusion The precise steps in this portion of the proof are 1 Hypothesis z gt 0 to Law of algebra VszVsz gt y A z gt 0 a 2 gt 342 where the universe of discourse for all variables is the set of real numbers 03 Universal instantiation m gt 0 A m gt 0 a m2 gt 0 Next we assume that z lt O Multiplying both sides of this inequality by z again yields z2 gt 0 since multiplying both sides of an inequality by a negative number reverses the comparison D Example Let f R a R be a linear function de ned by fz mz b for all z E R where m and b are real numbers and m 7 0 We will prove that f is one to one using a proof by contradiction We assume that f is not one to one Then there are real numbers 1 and 2 such that 1 7 2 and fx1 fx2 It follows that mxl b mxg b which simpli es to the equation mxl mxg Since in 7 O we can divide both sides by m to obtain the equation x1 x2 However this contradicts our assumption that x1 7 x2 Therefore f must be oneto one D Theorems and Quant i ers Many theorems are statements that include quanti ers We now describe some methods of proof that facilitate the process of establishing the truth of such statements 0 An existence proof is a proof of a statement of the form 3xPx for some predicate P Such a statement can be proven using a constructiue proof in which a speci c element x is found for which Px is true Alternatively one can use a nonconstructiue proof in which no speci c element x is found Typically this involves a proof by contradiction in which it is shown that HxP 7gt F o A uniqueness proof is used to show that there exists exactly one element x in the universe of discourse such that Px is true for some predicate P That is we prove the statement 3le00 AVyty 31g 90 H ePyl o A counterexample is an element x for which Px is false for some predicate P such an element can be used in a constructive proof of the statement VxPx In effect we are proving this statement by constructively proving the equivalent statement Hx Px We now illustrate some of these methods in the following examples Example Consider the statement The equation x2 7 x 7 1 0 has a solution between x 0 and x 277 To prove that this statement is true we must use an existence proof since it claims that there exists a number between 0 and 2 that is a solution of the given equation In this case a constructive proof would proceed by employing the quadratic formula to compute the solutions or roots of this equation which would reveal that one of the roots does in fact lie between 0 and 2 A nonconstructive proof can proceed as follows if we de ne the function f R 7 R by fx x2 7x 71 then f0 71 and f2 1 From calculus it is known that because the graph of f is a continuous curve every real number between f0 71 and f2 1 is the image of some real number between 0 and 2 Since 0 is between 71 and 1 it follows from universal instantiation that there exists some real number x between 0 and 2 such that fx x2 7 x 7 1 O D Example Let x0y0 be a point in the plane and let in be any real number We will show that there is exactly one line of slope in that passes through the point x0y0 This involves a uniqueness proof which often involves a proof by contradiction We assume that there are two distinct lines of slope in that pass through this point These lines have equations y mx 1 b1 and y mx 1 2 where 1 7 2 since the lines are assumed to be distinct Because they pass through x0 yo it follows that mxo 1 b1 mxo 1 b2 Simplifying this equation we obtain the equation Jim Lambers Math 6A Spring Quarter 200304 Lecture 16 Notes These notes correspond to Section 53 in the text Expected Value and Variance cont d We now continue our analysis of the behavior of random variables The Geometric Distribution The following probability distribution is useful in applications in which outcomes correspond to sequences of experiments that are in some sense failures until a single success occurs De nition Geometric Distribution A random variable X has a geometric distribution with parameter p ifpX k 1 7 pk 1p for each positive integer k Theorem IfX is a random variable that has a geometric distribution with parameter p then Example Suppose that a coin has a 110 chance in coming up heads We let X be a random variable with a geometric distribution with parameter p 110 on the sample space of sequences of coin ips that end with a result of heads Then for each positive integer k pX k is equal to the probability that a sequence of k coin ips will have k 7 1 tails and one head Because of our choice of sample space Xs k if and only if s is the sequence of k ips that ends with a result of heads From the preceding theorem EX 1110 10 so we expect that 10 ips are necessary before the coin comes up heads D Independent Random Variables De nition Independent Random Variables Let X and Y be random variables on a sample space S We say that X and Y are independent if pX8 71 A Y8 r2 pX8 71 WWW T2 for alls E S The following result provides a simple way of determining whether two random variables are independent Theorem IfX and Y are independent random variables on a sample space S then EXY Proof Since every value p in the range of XsYs is obtained by multiplying two values 71 E XS and r2 6 YS we have EXY pXY r TEXltSgtYltSgt Z Z pXs n A Ys T2T1T2 News news Z 2 MM T1T1pYs mm 7 16XS TQEYltSgt Z PXST1T1 Z PYST2T2 7 16XS WEE5 Z pltXltsgtngtnEltYgt 7 16XS Em Z pltXltsgtngtn 7 16XS EXEY D Example Let X1 and X2 be a random variables on a sample space S that have the same values for each outcome in S that is X1s X2s for all s E S We will show that if we rede ne the domain of X1 and X2 to be 2 S x S so that X1a 13 a and X2a 13 b for each ordered pair a b 6 52 then X1 and X2 must be independent Let i E X1S j E X2S and let p1 pX1 i p2 pX2 It fOllOWS that pX1 iAXZ p1p2 pX1 ipX2 which implies that X1 and X2 are independent D Variance The expected value by itself is not always a useful indicator of a random variables behavior on its sample space because it only indicates what number the values of the variable tend to cluster around To have a clearer picture of the variables behavior it is helpful to have a measure of how much the variables values deviate from the expected value We now state a precise de nition of this concept De nition Variance Let X be a random variable on a sample space S The variance of X denoted by VX 239s Example Let S 1 234 56 be a sample space consisting of equally likely outcomes of a roll of a single die and let X S a N be a random variable de ned by Xs s for all s E S representing the value of the roll corresponding to s Then using the fact that EX 35 as computed in the previous lecture we have 1 1 52 32 12 12 32 52 6 lt7 lt gt lt gt lt2gt lt gt lt gt i 125 9 1 1 9 25 ElIZZZZIl 7125 9 1 al7 l 7 35 E It follows that the standard deviation of X is 0X NBS12 x 17078 D The following results provide various techniques for computing variances that in some cases may be simpler than using the de nition directly Theorem IfX is a random variable on a sample space S then VX EX2 7 EX2 Proof We have D 23W 7 2EltXgtXltsgt EltXgt2gtpltsgt X82p8 7 Z 2EltXgtXltsgtpltsgt 21900229 XZ Z 2EXSps EX2 ps EltX2gti Z6b SltXgtZXltsgt1alts EX25613 EX2 2EX if EltXgt2 EX2 EX2 Example Let S 172374576 and let S2 S x S be a sample space that represents the outcomes of rolling two six sided dice7 where each number is equally likely to be rolled for each die Let X S2 a N be a random variable that assigns to each ordered pair 11 6 S2 the number a 1 b7 the sum of the two rolls Then EX 77 as computed in the Lecture 15 notes We also have EX2 Z X82p8 5652 Z Z 81 822P817 82 5165 9265 1 6 6 Z Z 81 822 511521 1 6 6 Z s 251s2s 1521 1 6 6 6 6 6 ZS lt21gt2281lt282gtZ 511 521 511 52 511521 6 6 H 1 6 661 81lt2gtZ 28 511 511 521 OJ 6 6 666 126 1 2 Z 81 66 1 66 126 1 2 6 6 6 l 6 69123 2 l ng 511 2 36 66 126 1 2 66 126 1 329 6 It follows from the preceding theorem that 329 35 749 6 6 VX EX2 EX2 D Theorem IfX and Y are independent random variables on a sample space S then VX Y VX VY Proof Since X and Y are independent7 EXY It follows that VX Y 7 ZXs ya 7 EX Y2ps 56 20 Y8 EX EY2p8 sES 206 EX2P3 238 EY2P5 565 565 2 EGGS EXYS EYp8 sES VX WY 2 EGGS EXYS EYp8 sES VX WY 2 ZlXSYS EXY8 EYX8 EXEYlp8 sES VX WY 7 2 ZX3Y3P3 21900 ZWSMS 565 565 2190 X8P8 2EXEY 2298 565 565 7 VX my 7 2 ZXSYsps 7 EXEY 7 EYEX EXEY sES VX VY 7 2 EXY 7 VX VY D Remark This result can be generalized to n independent random variables X17X27 7Xn on a sample spaces S Speci cally7 VX1 X2 Xn VX1 VX2 VXn 5 Jim Lambers Math 6A Spring Quarter 200304 Lecture 20 Notes These notes correspond to Section 32 in the text Sequences and Summations Sequences When working with a set it is often helpful to describe the elements of a set by numbering them For instance a set with four elements can be described using the notation a1a2ag a4 Such a numbering can be used to provide a concise description of all of the elements of the set which facilitates use of the set in the context of solVing problems As numbering elements effectively imposes an order on the elements we can View the numbered elements as forming a sequence We now de ne this concept precisely De nition Sequence A sequence is a function whose domain is a subset of Z the set of integers Each element of the range of the sequence is called a term of the sequence For each integer n in the domain of the sequence the image of n is denoted by an Remark Although a sequence is de ned as a function it is usually identi ed with its range which is the set of all of its terms That is a sequence with elements akak1ak2 am can be described using the notation an7k The notation an is also used when the domain of the sequence is understood from the contest We illustrate this identi cation of sequences in the following examples D The following two types of sequences are of particular interest De nition Geometric Progression A geometric progression is a sequence whose terms have the form a ar ar ar where a is a real number called the initial term and r is real number known as the common ratio De nition Arithmetic Progression An arithmetic progression is a sequence whose terms have the form a a d a 1 2d a 1 not where a is a real number called the initial term and d is real number known as the common difference Example Let a 1 and r 712 Then the geometric progression with initial term a and common ratio r contains the elements 1 712 14 718 116 This sequence can be described more concisely using the notation 712 ff0 or simply 712 when the length of the sequence is understood from the context D Example Suppose that a sequence beginning with the number 4 has elements that are spaced 5 apart that is the sequence has the elements 49 14 1924291 We can then recognize that this sequence is an arithmetic progression with initial term 4 and common difference 5 This sequence can be represented more concisely using the notation 4 5n D Summat ions Often it is necessary to determine the sum of the elements of a sequence an of numbers This may seem like a trivial task involving nothing more than the arithmetic of adding the numbers but this approach is not feasible if the sequence has in nitely many elements Even if the sequence is nite it may be possible to obtain a formula for the sum that is much easier to compute We have previously used the notation V L Z an lm to represent the sum am am an This notation is called summation notation or sigma notation due to the use of the Greek letter sigma The variable i is called the index of summation The number m is called the lower limit and the number n is called the upper limit The index of summation assumes the values of each integer between the lower limit and the upper limit and the sum includes all terms in the sequence an that are images of integers in this range Sums of elements of sequences are known as series which we now de ne precisely for both nite and in nite sequences De nition Series Let an be a sequence The sum n E 047 im for any integers in and n is called a series If the domain of an is the set of all integers not less than m then the sum 00 Z w im represents the sum of all terms of the sequence This sum is called an in nite series Each term a of the sequence an is called a term of the series Example Let anff0 be a sequence in which each term an has the form znnl where z is a real number Then the series 00 n E x l 0 71 is an in nite series The sum of this series is expm or em which is the value of the natural exponential function at z D The following result illustrates how7 in some cases7 the sum of the terms in a series can be represented using a simple formula that is largely independent of the individual terms Such a formula is known as a closed form TheoremSum of Geometric Series fa and r are real numbers then n n17 Zarj aTT 11 Tf l j0 an 1 T 1 Proof If r 17 then the sum consists of n 1 terms that are all equal to 017 so clearly the sum is an 1 Suppose that r 7 1 Let 71 S Zarj 70 Then we have 70 70 TL 71 a 27711 7 Z 77 70 70 n1 n a Z 7 Z 71 70 a Z rn1 12 71 73971 a TWA 7 1 By factoring the left side into Sr 7 1 and dividing by r 7 17 we obtain VH1 7 1 7 a r 7 1 and the proof is complete Note that the division by r 7 1 is valid because we are assuming that r 7 1 D The following table includes some useful formulas involving summations Note how the previous result can easily be generalized to in nite geometric series when the common ratio is less than 1 in magnitude Jim Lambers Math 6A Spring Quarter 200304 Lecture 27 Notes These notes correspond to Section 65 in the text InclusionExclusion ln Lecture 7 we learned a useful technique for counting problems called the inclusion exclusion principle In its simplest form the principle states that given two sets A1 and A2 A1 U Agl 7 Al 7 lntuitively this principle states that the number of ways to complete two tasks when the tasks can possibly be performed at the same time is equal to the sum of the number of ways to perform each task less the number of ways to perform both An alternative interpretation is that the number of objects that have either one of two properties is equal to the sum of the number of objects that have each property less the number of objects that have both properties This principle can easily be generalized to count the number of objects in the union of three sets A1 A2 and A3 Using the formula for the cardinality of the union of two sets along with the Distributive Laws and the Associative Laws we obtain lAl o A2 o Agl lAl o A2 o A3l lA1l lAg o Agl 7 lAl A2 oA3l lA1l lA2l lA3l7 lAz A3l7lA1 142 U ASH lA1l lA2l lA3l7 lAz Asl 7 W11 A2 U A1 A3l lA1l lA2l lA3l7 lAz Asl 7 lAl A2llA1 Agl 7 lA1 A2 A1 ABM lA1l lA2l lA3l7 lAz Asl 7 H141 A2llA1 A3l7lA1 A2 Agl lA1l lA2l lA3l7 lAl A2l7lA1 Agl 7 lAz Agl lAl A2 Agl Note that the formula for lAl U A2 U Agl involves the cardinality of the intersections of pairs of sets chosen from A1 A2 A3 as well as the intersection of all three sets Also note that the cardinality of the intersections of pairs of sets is subtracted while the cardinality of the intersection of all three is added We will now state and prove the general inclusion exclusion principle that counts the number of elements in the union of n sets A1 A2 An To state the formula concisely we introduce some notation Let Sn 1 2 n be the set of the rst n positive integers We de ne OAS to be the set containing all r combinations of elements of Sn Each r combination s E CNS contains r distinct integers chosen from Sn which we denote by 81 32 3 Theorem Inclusion Exclusion Principle Let Sn 1 2 n If A1 A2 An are sets then 84 2 ms 71 seams 71 n i1 where 075 is the set of all r combinations of the set 5 and each r combination s 6 075 contains distinct elements 31 32 sr chosen from Sn Proof We must show that each element in the union of A1 A2 An is counted exactly once by the formula stated in the theorem Suppose that an element a belongs to r of these sets Then it is counted r times by the sum lAll lAgl Since there are Cr 2 ways to choose two of the r sets to which a belongs it follows that a is counted Cr 2 times by the sum of the cardinalities of the intersections of all pairs of sets In general a is counted Cr k times by the sum of the cardinalities of the intersections of all combinations of k sets for k 1 2 T It follows that the number of times a is counted in the formula in the statement of the theorem is Cr 1 7 Cr 2 093 711CT r i71k10rk k1 However ZEDkCMk 7 k0 which yields 7 7 ZEDWCM k 7271k0nk 71OCT7017 k1 k1 so we conclude that a is counted exactly once Since r is arbitrary it follows that every element of the union is counted exactly once so the formula computes the cardinality of the union correctly As in the case of three sets the cardinality of the union of n sets is obtained by computing the cardinality of intersections of larger and larger combinations of sets beginning with single sets then pairs of sets and so on until the cardinality of the intersection of all n sets is included Cardinalities of intersections of an even number of sets are subtracted while cardinalities of intersections of an odd number of sets are added Example Given four sets 141142143 and A4 the inclusion exclusion principle states that 1A1 0A2 0A3 0144 1A111A211A31 114417 Vim12171141 A3171A1 A4l 7 Vim1317 Ag AM lAg A4l lAl Ag Agl lAl Ag A4l lAl Ag A4l lAg Ag A4l7 Al Ag Ag A4 D Remark In applying the inclusion exclusion principle to 71 sets it is necessary to enumerate all r combinations of the set Sn 1 2 n for r 1 2 n One can enumerate all of the r combinations for a given r using a recursive process The following algorithm describes this process of computing the set CNS used in the preceding theorem f0ri1t0n7r1d0 A i LetTijlj SnAjgti for each B E 07713 10 AAUB 030 030 U A end end In words this algorithm builds r combinations of elements of Sn by choosing an element i of Sn and then adding r 7 1 combinations of elements greater than i This ensures that each combination is included only once D The general inclusion exclusion principle provides a technique for counting the number of objects that have one or more properties given that it is possible that some objects may have more than one of these properties We now illustrate the use of the inclusion exclusion principle for solving such counting problems Example We use the inclusion exclusion principle to compute how many positive integers not exceeding 1000 are divisible either by 4 8 or 10 Because 1000 is divisible by all of these numbers it is easy to determine that there are 250 such numbers that are divisible by 4 125 that are divisible by 8 and 100 that are divisible by 10 Now we must exclude numbers that are divisible by more than one of 4 8 or 10 Let A4 A8 and A10 be the sets of numbers that are divisible by 4 8 and 10 respectively Since 8 is divisible Jim Lambers Math 6A Spring Quarter 200304 Lecture 22 Examples This example corresponds to Section 61 in the text Example Exercise 23a Section 61 Find a recurrence relation that describes the number of bit strings of length n that have two consecutive zeros Solution Let an be the number of bit strings of length n that have two consecutive zeros where n is a nonnegative integer To nd a recurrence relation that is satis ed by an we must determine how an can be computed if we know 1771 an and so on This is equivalent to determining how bit strings of length n that have two consecutive zeros can be obtained from strings of shorter length A bit string of length n 7 1 is extended to a bit string of length n by adding a 0 or a 1 Furthermore such a bit string of length n 7 1 may or may not have two consecutive zeros It follows that all bit strings of length 71 fall into exactly one of four categories H Strings that have two consecutive zeros in their rst 71 7 1 bits and end with a 0 to Strings that have two consecutive zeros in their rst 71 7 1 bits and end with a 1 03 Strings that do not have two consecutive zeros in their rst 71 7 1 bits and end with a 0 F Strings that do not have two consecutive zeros in their rst 71 7 1 bits and end with a 1 Strings in the fourth category cannot have two consecutive zeros so we do not need to consider them The remaining strings can be described using ony two categories 1 Strings that have two consecutive zeros in their rst 71 7 1 bits and end with a 1 2 All strings that end with a 0 The rst category contains an1 strings because they have two consecutive zeros among their rst 71 7 1 bits Therefore this category contributes an1 toward an The second category must be examined further We can decompose it into four categories as we did before 1 Strings that have two consecutive zeros in their rst 71 7 2 bits and end with a 00 2 Strings that have two consecutive zeros in their rst 71 7 2 bits and end with a 10 3 Strings that do not have two consecutive zeros in their rst 71 7 2 bits and end with a 00 Jim Lambers Math 6A Spring Quarter 200304 Lecture 22 Notes These notes correspond to Section 61 in the text Recurrence Relations There are many counting problems for which the techniques we have previously studied are not useful In the remaining lectures we will discuss various advanced techniques for solving such problems As counting problems are concerned with determining the cardinality of various sets we begin with the use of recursion to describe sets and by extension compute their cardinalities The basic idea is to de ne a set Sn whose contents depend on the integer n in terms of sets of the form Sk for some integer k lt n Then is an integer valued function of n that is a recursively de ned function as discussed in the previous lecture In this lecture we will focus on the task of constructing functions recursively that describe the cardinality of such a set Then we will consider the problem of obtaining an explicit de nition of a recursively de ned function since an explicit de nition while more dif cult to obtain is usually more ef cient to evaluate especially for large values of n In a recursive de nition of a function f A a B certain initial ualues of the function must be de ned explicitly for the basis step of the de nition The recursive step describes how u for any x E A that is not already considered in the basis step is to be computed using values of 1 corresponding to other elements of A Typically x is related to the other function values by an equation which we now describe precisely De nition Recurrence Relation Let an io be a sequence A recurrence relation is an equa tion that relates an to an1 an2 0W for some xed integer k and each n 2 no where no is a nonnegatiue integer A sequence whose terms satisfy a recurrence relation is called a solution of the recurrence relation Example The sequence of Fibonacci numbers fnf0 introduced in the previous lecture is de ned by the simple recurrence relation in fnil fn727 71 Z 27 with f0 Oand f1 1 D Modeling with Recurrence Relations In the following examples we illustrate how the problem of counting the number of elements in various sets can be solved more easily by describing these sets using recurrence relations rather than using techniques such as the Product Rule and the Sum Rule to count the number of ways in which elements can be constructed Example Suppose that pairs of rabbits where each pair consists of a male and female rabbit reproduce in such a way that each pair that is at least two months old gives birth to a new pair every month If initially there is one newborn pair how many pairs are there after 71 months for any nonnegative integer 71 Let Tn be the number of pairs after 71 months This number must include the number of pairs that existed in the previous month denoted by MA Furthermore fn must include any pairs that were born in the nth month The number of newborn pairs is equal to the number of pairs that are at least two months old since each such pair gives birth to another pair This number is 76772 the number of pairs that existed two months ago It follows that m M71 M72 In other words the sequence m is the sequence of Fibonacci numbers with To 1 and r1 1 since there was initially one newborn pair that had to wait two months to reproduce This sequence is essentially identical to the Fibonacci sequence fn de ned above in that for each n 2 1 fn Tnil D Example A popular problem pertains to the Towers of Hanoi The towers are three pegs with disks of different sizes that can be stacked on the pegs The problem is as follows given 71 disks of 71 different sizes stacked on one peg such that each disk is larger than the one above it how many moves are needed to transfer all of the disks to one of the other pegs in such a way that a larger disk is never placed on top of a smaller disk Let Hn be the number of moves needed and let the three pegs be numbered as peg 1 peg 2 and peg 3 We assume that the disks are initially stacked on peg 1 and they must be moved to peg 3 The problem of moving the n disks can be solved as follows in order to move the largest disk that is at the bottom of the stack at peg 1 the stack at peg 3 must be empty and no other disks can be stacked at peg 1 Therefore the other 71 7 1 disks must be stacked in order of size on peg 2 Then the largest disk is moved to peg 3 and then we must solve the problem of moving the other 71 7 1 disks from peg 2 to peg 3 In short we have reduced the problem of moving n disks to two problems in which n 7 1 disks must be moved Therefore Hn satis es the recurrence relation Hn 2111771 1 Jim Lambers Math 6A Spring Quarter 200304 Lecture 16 Examples These examples correspond to Section 53 in the text Example Suppose that we need to sort 71 real numbers m1 m2 Wm in ascending order We are using the algorithm known as insertion sort This algorithm copies the numbers in an array A7 of size n to another array B7 also of size 71 one at a time in such a way that B is always sorted lt maintains the sorted order in B by shifting elements as needed when a new one is added The following pseudo code describes how insertion sort can be implemented for i 1 to 71 10 j i 7 1 while j 2 1 and BM gt d0 Bj 1 Bj shift element to make room for new element j j i 1 BU place new element in correct position One way to measure the complexity of this algorithm is in terms of the number of times elements need to be shifted in order to maintain the sorted order of B In the best case7 when the array A is already sorted7 no shifting is required In the worst case7 when A is sorted in descending order7 if 1 shifts are required to place the ith element of A in the correct position within B7 so the total number of shifts is 2 1 7 271227217n 39 1 i1 i1 M What is the averagecase complexity of this algorithm Solution Let S be the sample space of possible inputs of size n that is7 each input is a list of 71 numbers to be sorted Assume that each possible ordering is equally likely If X is a random variable whose value for each input is the number of times elements need to be shifted7 then the average case complexity is given by EX For each i 127 771 let X be the random variable whose value is the number of shifts required to place the ith element of A in the proper position in B Then X can assume any value between 0 and i 7 17 corresponding to the best case and worst case7 respectively If we assume that each value of Xi is equally likely then we have 171 EXi pXijj 70 i711 7 j0 1i1 j 20 i 1 71 711 i 2 7 1271i 2 2 7 iil 2 Since X X1 I X2 I I X it follows from the linearity of expectations that II II EX EXz39 II M I H W H M D I m H s N 3 3 H C I i 3 HH H 3 NIH NIH NIH Therefore the average case complexity is approximately one half that of the worst case complexity D Example Let S 1 2 3 4 5 6 be the sample space of equally likely outcomes of the roll of a single die and let X be the random variable de ned by Xs s for all s E S What is VX Solution In the Lecture 15 notes we computed EX 35 To compute VX we can use the formula VX EX2 H EX2 which yields 182 147 E 7 E 35 E D Example Let S be the sample space from the previous example7 and let S2 S x S be the sample space of all possible outcomes of the rolls of two dice7 where each outcome is equally likely Let X be the random variable on S2 de ned by Xoz7 b a b for each ordered pair 017 b 6 S2 What is VX Solution Let X1 and X2 be random variables de ned on S2 whose values at each ordered pair 11 6 S2 are de ned to be X1ab a and X2ab b That is7 X1 and X2 are the values of the rolls of the rst and second dice7 respectively Then X X1 X2 Before computing VX7 we rst show that X1 and X2 are have one property that independent variables have EX1EX2 EX1X2 We note that EX1 EX2 357 and then we have EX1X2 2X18X28P8 9652 Jim Lambers Math 6A Spring Quarter 200304 Lecture 18 Notes These notes correspond to Section 33 in the text Mathematical Induction In the previous lecture we learned about the rule of inference known as uniuersal generalization which stated that if Pc is true for an arbitrary element c in the universe of discourse then the statement VmPz is true In practice however it can be difficult to prove that a predicate Pm is true for an arbitrary element m In this lecture we will learn one technique for accomplishing this task in the case where the universe of discourse is 2 the set of all positive integers This technique which is a rule of inference called mathematical induction is used to prove that a statement that has a positive integer n for a parameter is true for all possible values of that parameter Because of its paradoxical combination of both power and simplicity mathematical induction has become one of the most widely used proof techniques in mathematics While mathematical induction is used within mathematics to prove that existing formulas are true as opposed to aiding in the discovery of new formulas it has been used for more constructive purposes within computer science in the area of algorithm design In this context mathematical induction is used to prove that a problem can be solved for an arbitrary input and the proof suggests an algorithm for obtaining a solution in such a way that it can easily be implemented We will demonstrate this use of mathematical induction in the next lecture The WellOrdering Property Before we state the principle of mathematical induction we introduce an important axiom of the natural numbers An axiom is a fundamental assumption that is generally accepted without proof and is usually sufficiently intuitive so that one can accept it as true without proof The following axiom will be used to prove that the technique of mathematical induction is in fact a valid rule of inference Axiom Well Ordering Property If S is a nonempty set of natural numbers then S has a least element That is there exists a natural number m E S such that n 2 m for all n E S lntuitively it makes sense that the natural numbers have this property that is to say the natural numbers are well ordered This is because the natural numbers themselves have a least element namely zero so any subset of N should have a least element as well The Principle of Mathematical Induction We are now ready to state the rule of inference for mathematical induction and prove its validity Theorem Mathematical Induction Let Pn be a predicate and let the universe of discourse for n be 2 the set of all positiue integers Then P1 AVnPn gt Pn 1 gt VnPn Proof Suppose that the hypotheses of the above implication is true that is P1 is true and Pn a Pn 1 for all n 6 2 Let S Q 2 be the set k 1 Pk and assume that S is nonempty that is we assume that Pn is false for at least one value of n By the Well Ordering Property it has a least element h It follows that k gt 1 since P1 is true It also follows that Pk 7 1 is true since otherwise k would not be the least element of S However Pk 7 1 implies Pk which contradicts our assumption that Pk is false Therefore the set S must be empty and Pn is true for all n 6 2 D We now examine how this rule of inference can be used to prove that a statement Pn is true for all n 6 2 The two propositions of the conjunction in the rule s hypothesis suggest the steps that must be followed First we must show that P1 is true This step is called the basis step or the base case Then we must show that if Pn is true for an arbitrary n 2 1 then Pn 1 is true as well This step is called the induction step or inductiue step and the assumption that Pn is true for an arbitrary n 2 1 is called the induction hypothesis Once the basis step and the induction step are complete then we can apply the rule of mathematical induction to conclude that Pn is true for all n 6 2 To see intuitively why this two step process is suf cient to prove that Pn is true for all n one can associate each particular statement Pn for each xed value of n with a domino and associate the statement Pn is true77 with the domino being knocked down It follows that the set Pn 1 n 6 2 is associated with an in nitely long sequence of dominos and if Pn is true for all n then all of the dominos are knocked down By carrying out the basis step and showing that P1 is true we are knocking down the rst domino The inductive step implies that if any domino is knocked down the next domino is knocked down as well These two statements taken together imply that every domino will be knocked down because the rst will cause the second to fall which in turn will cause the third to fall and so on Examples of Proofs by Mathematical Induction We now illustrate the use of mathematical induction in proofs Example We prove the formula 71 1 D m n 2 1 2 11 First we perform the basis step corresponding to n 1 The sum of the integers from 1 to 1 is simply 1 and 1112 1 22 1 so the formula holds in this case For the induction step we assume that the formula holds for some arbitrary n 2 1 and show that it holds for n 1 That is we assume 2 i1 47nn1 T for some n 2 1 and show that this implies that it n1n2 2 2 11 for this same value of 71 Because 71 is arbitrary and the formula holds for n 1 this induction step will prove that the formula holds for all n 2 1 For the induction step we have 3 H H in1 H H tn t1 nn1 2n2 2 2 n2n2n2 2 n23n2 2 n1n2 2 3 3 This completes the induction step By the principle of mathematical induction since the formula holds for n 1 and the fact that it holds for an arbitrary n 2 1 implies that it holds for n 1 it must hold for all n 2 1 D Mathematical induction is often useful for generalizing formulas that apply to an input of size 2 to an input of size n for any positive integer n We illustrate this use in the following example Example In Lecture 15 we proved that if X1 and X2 are random variables de ned on a sample space S and X X1 X2 then EX EX1 EX2 We now use mathematical induction to prove that if X X1 X2 X where n 2 2 and X1 X2 Xn are any 71 random variables de ned on S then 1900 EX1 EX2 EX The basis step corresponds to n 2 In this case we have X X1 X2 and we proved in the Lecture 15 notes that EX EX1 EX2 For the induction step we assume that the above sum holds for an arbitrary n 2 1 and show that it holds for n 1 That is we assume that 71 71 E Xgt ZEX i1 i1 and will show that this implies n1 n1 E Xgt ZEX i1 i1 where Xn1 is any random variable de ned on S We have Eqixi E gtEltXn1 EXi EXn1 H M W H EX H Note that the case of n 2 from the basis step was used in the second step above to decompose the expectation of the variable X1 X2 Xn1 into the sum of the expectations of two random variables X1 X2 Xn and Xn1 The induction hypothesis was then applied in the third step to the variable X1 X2 X D Remark Note that in the preceding example we proved that the statement the expectation of the sum of 71 random variables is equal to the sum of their expectations ICS 6B Boolean Algebra amp Logic m r Lecture Notes for Summer Quarter 2008 Michele Rousseau Set 5 Ch 81 82 83 Today s Lecture 0 ChapterB 8182 33 a Relations and their properties 81 nary relations and their applications 82 Transitive Property LetA be a set and R be a relation on setA is if 397 then quot39 forall V o In other words R is transitive i VxVszKx y EK l y z EK gt x 2 ex and one from then there must be one from A This is the most dif cult one to check Lets Announcements I 0 Quiz 3 Thursday 0 Will cover 22 23 81 82 83 W o Homeworkis online 0 Regrades 0 Please look over your quizzeshomeworks carefully o Quizzes 1 8L 2 8L Homeworks 123 need to be h turned in by Thursday 0 Iffor some reason you can39t turn them in by thurs let me know no later than thurs 82 83 2 Chapter 8 Section 81 nut m Relations and their properties Transitive Examples Eg gt It x gty 8 ygt z thenisxgtz 3gt2A 2gt1 3gt1 YesTmnsitlve E339 h Ifx y 8 y z theuisx z 1 2A21 b11 NoNot39l mnsitive 82 83 a Transitive Example 2 Consider the relations on 1234 4 3 3 2 a i 5 a E F l R1 14 25 35 14 2536 5 1 6 2 1 Ra y b v001 i 390 A sV I W 100 00 I z 5 39 RI4 no 100311 hd i r h c Rs213132414243 2 x wg 1 3 2 2 1 4 4 2 21 fromAm E aresubsetsofoB R2 can be combined the same Rz i1415162l 1415162l 2536 X DZ 3 1 4 1 4 2 songt9 1 Transitive Example 3 Consider the relations on 1234 Rs111213212Z1333M lo 2 1 1 3 2 3 Composite n n a Notations S o R a In other words Let Rbe arelau39onfrom setAto B 8 S be a relation from set B to C then So RistherelationfromAto C provided 1 exists ab 6 R and 175 E S u m mm m 5mm E Composite Example 2 A R gt E S gtC x R11 1 3l 3 LO31 5111 2212Z 1 xs L z 1 a 1 4 zz224 1 s Using Relation of Composition to I Check if a Relation is Transitive De nition W Let R be a relation on the set A The powers R n123 are de ned recursively by R1R and Rn Ru 0 R Theorem39 The relation R on setA is 8283 is dilution The induction hypothesis I assume true for nquot so assume R S R Showitmustbetrue forn 1 n n So if acE R 1 then there exist a b such that ab e Rn and bc e R by de nition ofcomposite We want to prove that acE R using the fact that R is ham ve By the inductive hypothesis R R So 31 E R and bcE R then ac e R by transitivity We just showed that any ac E R 1 belongs to R So Rn1 S R OED Take a break 0 Stretch Relax 0 Get some water Usethe restroom o Getto know your classmates o When we o 82 nary relatlons and their applications i Lecture Notes 57 Important Proof R m w if R E R Proof by lnductlon 0 Assume Rlsm w 0 New show R E R byindm au Basis Showitis trueforn 1 o R1 R so R R 7 Nothing to prove in 82 83 it Homework 81 0 1abC 3 3390 573Ceg9 28 30 3 5 a c e g Chapter 8 Section 82 Elli nary relations and their applications n ary relations Primary Keys 9 Ianealwrelamnofdegeen 1e msasuhseiomxA2x RAquot a AA2 Aquot are the domains lt 3 v1 h The domain A715 the rimary key for R ifwe can l This is only possible no two nrtuples are the s Ihe nrtuple an he identi ed bythatdomain Composite Key 0 A mmpasimlmyis a set of keys uniquely identify the ntuples o It is derived by the Cartesian pro u ofthe tuples that uniquelyidenti nrtuples some c m mm Ihe elemems of R are nrtuples 3 aw 3quot wnh distinguish the nrtupes m R by making aune jth ehuy 0 In m w oApr arykey 39 isadomainthatcanactas a unique identl er the nmplec ame lat d ct fy the 39splaying nary Relations w Table hle zenmag Ta movessnr Ruusseau 3 1 imma39x Dmencoun cs Ruusseau Math s a s 31 i m immm NM M ofcolumns 3 gt Columns ambune 0 Rum ofnrtuples m R 5 gtR mm Al Professor A2 DeptA3 Course No Rousseauin4matXiNF111 DillencourtCSJCSl l Rousseau athMaLhEB SudaCSiCSlSlZivin4matXiNF131 0 Each ehuy m the nrtuple is a eld In Primary Key Example T 39 39 39 k 3 X lNFMi 1 Diiiencuu cs iCS 61 Ml Ruusseau Math MathEE 1 Shoe cs loam 2N inbmatx NFW o What are the Domains H o Whichoouldbea ryKey E ems one x m 22 Operations on nary Relations 0 Selection Operator allows you to select n tuples from a Inble that satisfy some condition you to form new nary relations ie a new table from a pre eidsling table by deleting the same elds in every record of the relation removing rowscolumns 0 Join o Allows you to combine two mines into one when the share some identical elds 2 D Selection Operator Notation 5C In other words Given a Iahle Select on the rows and columns that satisfy the condi on The pm on Where mapslhe nluplea v a mluple a a2 am Where m i lt iltlt olhe H x o In otherwords 0 Delete the columns in the ith position de ned by R amp s have the same number of records rows H a R amp s have p attributes in common p ldenucal 0315 last p H columns ofRagree wnh the rstP columns ofS 9 E 5 3 an 5 s 5 Example 7 Selection Operator Asdgum bl Drnmwr muss u namatx mm Dmonco mm H Ruusseau MathEE s a 03151 l ZN momam Wm S where C1 is the condition In4matX Department l gtThe resultis atx NHM nu Ruusseau lmm zw mmax Nrm looms m 58 on an Projection Example T ble39 39 39 a mm W Dlllencuun cs 03161 an o MathBE vquotl Suda l 3151 my son Ruusseau mmax mo nun cs H Join Example Table MAMA Table locum non rnmseuu m Ruusseau lnwmtx lNFlM NFlM ELHlEIEI BEIEIa Dlllencuun CS cswm lCSlEl DEHl UU llUUa Ruu eau Malh MalhBE MalhBE DEnglEI l p x g kid K77 wruvessm mu m W RESP monsoon cs loam oomoo M a Romeo Mam MathBE oowoo l p Homework 82 0 357 arc9 arc111719 lull Chapter 8 Section 83 MirIii Representing Relations Representing Binary Relations 0 By Matrices 01 0 By Directed Graphs lemma c 5mg Examgele Relation as a Matrix Weamm mmlabeledwl nheelemmofn Indthemlummlr hbeledwi nh elemzmsnf Using Matrices Let Rhe a relation from Aaiazam to Bh1b2b R is a subset anx B 50 elements of R are pairs of the form 51th nu Mei 1 nu I We assosciate R m the matrix MR as follows Theorem Let Rbe a binary reladnn on a setA and let M be its connection matrix Then okisre advei m1rurani e nmwmmmici MixawmmmicmauizmmT o Risan wmmekicifMu00eri0faralli i 913

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.