Applied Combinatorics MATH 3012
Popular in Course
Chelsea Nolan MD
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
EXSC 223 001
verified elite notetaker
Popular in Mathematics (M)
This 0 page Class Notes was uploaded by Chelsea Nolan MD on Monday November 2, 2015. The Class Notes belongs to MATH 3012 at Georgia Institute of Technology - Main Campus taught by Thang Le in Fall. Since its upload, it has received 22 views. For similar materials see /class/233953/math-3012-georgia-institute-of-technology-main-campus in Mathematics (M) at Georgia Institute of Technology - Main Campus.
Reviews for Applied Combinatorics
Report this Material
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: 11/02/15
Math 3012 Applied Combinatorics notes Alex Whitney June 29 2007 Contents 1 May 14 2007 11 Introductory Notes Fundamental Rules of Counting 121 The Rule of Sums 122 The Rule of Products Permutations 12 13 2 May 162007 21 Combinations 211 Binomial Coefficient 212 Multinomial Coefficient Binomial Theorem Multinomial Theorem 22 23 3 May 19 2007 31 Combinations and Permutations with Repetition 4 May 21 2007 41 Induction 42 Division Algorithm U1 May 23 2007 51 Division Algorithm continued 52 Euclidean Algorithm 53 Additional Proofs 6 May 252007 61 Cartesian cross Product CONTENTS 1 8 9 10 11 13 14 62 63 Relations Functions Mapping 631 One to OneInjective 632 Onto functions Bijection Pigeonhole Principle 64 65 May 30 2007 71 Principle of Inclusion and Exclusion 711 Set Notation 72 June 1 2007 June 4 2007 81 Derangements Continued 82 Rook Polynomials 83 Mathematical Definition 84 Computing Rook Polynomials June 6 2007 91 Arrangements with Forbidden Positions June 13 2007 Reformat 101 Introduction to Generating Functions 102 Formulas for Series June 15 2007 Reformat 111 Partial Fraction Decomposition 112 Application of Partial Fractions May 18 2007 121 Exponential Generating Functions 122 More Infinite Series Formulas June 20 2007 131 The Summation Operation June 22 2007 Reformat 141 Recurrence Relations 142 Non Constant Recurrence Relations 21 21 22 22 24 CONTENTS 3 143 37 15 June 25 2007 Reformat 39 151 Second Order Linear Constant Coefficient Recurrence Rela tions 39 16 June 27 2007 reformat 41 161 Review 41 162 Non Homogeneous Recurrence Relations 41 1621 Steps to solving a non homogeneous recurrence re lation 43 17 June 29 2007 reformat 45 171 Combining Generating Functions and Recurrence Relations 45 172 Using Generating Functions to Problems We Can39t Already Solve 46 173 Additional Formulas 46 Lecture 1 May 14 2007 11 Introductory Notes 0 Formula sheets are allowed on exams but no calculators 0 Test one covers chapters 1 4 5 and 8 Basic Counting Methods 0 Test two covers chapters 9 10 and 11 Advanced Counting Methods basic graph theory 0 The final covers 12 and 13 in addition to the previous materials Optimization on Graph theory 12 Fundamental Rules of Counting 121 The Rule of Sums Rule of Sums If the possible outcomes of A can be divided into two dis joint sets B and C then A B C Example 121 There are two barrels of apples The first barrel has 10 apples and the second barrel has 8 apples A person walks by and selects an apple from a barrel How many di erent apples could the person have selected Solution The apples in each barrel are disjoint that is to say that any apple in the first barrel cannot be in the second barrel and vice versa The LECTURE 1 MAY 14 2007 5 problem canbe split into two parts The first part is the number of different apples the person could select from the first barrel and the second part is the number of different apples the person could select from the second barrel Part 1 10 different apples Part 2 8 different apples By the rule of sums the total number of different apples the person could have selected is 10 8 18 122 The Rule of Products Rule of Products If the possible outcomes of A can be performed in two independent stages B and C then A B gt C Example 122 A six sided die is rolled and the result is recorded The die is then rolled again and the new result recorded Find the number of outcomes for this procedure Solution There procedure is performed in two stages rolling the die the first time and rolling the die the second time The result of the first stage has no effect on the result of the second stage so the two stages are independent Part 1 Stage 1 6 results Stage 2 6 results By the rule of products the number of results for the given procedure is 6 a 6 36 13 Permutations Permutation Given n distinct objects any linear arrangement of the objects is called a permutation of the n objects LECTURE 1 MAY 14 2007 6 Example 131 A coin is ipped and the result is recorded The coin is ipped again and the result recorded List all of the permutations for this procedure Solution HH HT TH TT rpermutations of n The number of permutations of all subsets of r objects from a set of n distinct objects is given by the equation 11 PM m Lecture 2 May 16 2007 21 Combinations rcombinations of n An r combination of n objects is a subset of r distinct objects from n Example 211 List all of the possible Zrcoinbinations of 1 2 3 Solution 12 13 23 211 Binomial Coef cient Theorem 211 Binomial Coefficient The number of ncoinbinations of n dis tinct objects is equal to n n rn r r 212 Multinomial Coef cient Theorem 212 Multinomial Coefficient Given n objects from k classes the objects in each class are identical then the number of unique permutations of n is equal to LECTURE 2 MAY 16 2007 8 n39 n nllnzlnk n1n2nk Example 212 Find the number of unique permutations of the letters in CAL CULATOR Solution 10 10 222 22 Binomial Theorem Theorem 221 Binomial Theorem x yquot Z 1xkyn k k0 23 Multinomial Theorem Theorem 231 Multinomial Theorem 11 x1x2xkquot n n nx71 x2xk n1n2wn3n 1 2 39 39 39 k Lecture 3 May 19 2007 31 Combinations and Permutations with Repe tition Example 311 Give the number of combinations of 5 objects from s1s2s3 with replacement Solution There are 3 classes and we are selecting 5 objects We can rep resent any given combination by using a notation of crosses and bars For example s cs c I s cs cs c I would indicate that there are two objects from the first class three objects from the second class and zero objects from the third class Looking at a combination in this manner there are seven possible positions for either a star or a bar In order to create a combination we only need to fix the positions of bars or stars Since there are 5 3 1 7 positions and we are fixing 3 1 2 bars there are a total of combinations This can be applied to a general case Theorem 311 The number of combinations of n objects from r classes is equal to 1l have also heard this called stars and bars and balls and buckets LECTURE 3 MAY 19 2007 nr 1 r 1 Example 312 Find the number of combinations of 10 objects selected from 3 classes with at most two objects from the first class Solution Numberinfirst class 0 1024 31 1 111 11 92 1 10 21 1 10 82 1 9 2 2 1 1 9 By the rule of sums the number of combinations of 10 objets from three classes is 11 10 9 30 Example 313 Find the number of nonrnegotive integer solutions to x1 x2x3 10 x1 S 2 Solution The solution to Example 313 is the same as the solution to Ex ample 312 If x1 x2 x3 are the classes then we are selecting 10 objects from the three classes with at most 2 selections from the first class Therefore the answer is 30 Lecture 4 May 21 2007 41 Induction The principle of induction is used to prove a claim for all Values greater than or equal to a base case Many mathematical principles can be proven with induction Weak Principle of Induction To prove Sn first prove Sn for abase case no Assume S k holds for all k then show that Sk 1 holds If Sn0 and Sk 1 hold then Sn holds for all n nn1 Example411 ProveO123n 2 using induction Solution Proof by induction kk1 Hypothesls Sk 0123k TVk20 Basen0 00OZ1 0 Stepnk1 w20123mk h k1 11 LECTURE 4 MAY 21 2007 12 kk12k1 kk2 1 2k 3 1 2 k1k11 2 Byinduction0123nNHZO El Strong Principle of Induction To prove Sn first prove Sn for a base case no Assume Sk holds for all values between no and k then show that Sk 1 holds If 5n0 and Sk 1 hold then Sn holds for all 11 Example 412 Prove that every integer n 2 2 is a product of primes Solution Proof by induction Hypothesis Pn pq n where pq are prime and k S n 2 2 n e Z Basen2 P22gt12 Step Pk 1 pq If k 1 is prime then k 1 is a product of primes If k 1 is not prime k 1 pq where 2 S p q S k p and q are product of primes so pq is a product of primes By induction n is a product of primes V11 2 2 El 42 Division Algorithm b divides a Given a b e Z and b i 0 then b a if a mb where m e Z If this is true then it is said that b divides a Lemma 421 Ifb a and C b then C a LECTURE 4 MAY 21 2007 13 Proof Sincebla3m Zsuchthata mb Sinceclb3n EZsuchthatb nc Therefore a mnc mna so C a El Theorem 422 Division Algorithm V 0117 6 Z with b gt 0 3 qr e Z such thata2qgtbrwithOSrS b Lecture 5 May 23 2007 51 Division Algorithm continued Theorem 511 For a given a b e Z 17 gt 0 3 a unique qr e Z suCh that aqbr0 rltb 52 Euclidean Algorithm Used to find the greatest common divisors GCD of two given integers Common Divisors C is a common divisor of a and b if C a and C b where C i 0 GCD C gt 0 is the greatest common divisor GCD of a and b if C is a common divisor of both a and B and V d a d b gt d C If C is a GCD of a and b then it can be written that C nga b nga0 loll a i 0 Theorem 521 V a b 6 2 3 a unique C 6 2 suCh that C ngab Proof 5 satbgt0st Z Take a value C e S which is the smallest element in S This value is unique C sa tbfor some 51 6 Z lfdlaanddlbthendsaanddltbs0d satb dC Suppose C Jf a then 14 LECTURE 5 MAY 23 2007 15 d qc r 0 lt r lt C by division alg r d qc rd qsdth r 1 qsd qth r s d t h Contradiction El LrES Theorem 522 Euclidean Algorithm Given a h e Z Letrozdr1h Ti 117141 m2 0 S n2 lt n1 51101 n1 ngUiu zn This process is repeated until rklz 0 Work backwards until you get back to gcdd 17 Example 521 Find the GCD of1024 and 28 Find s t so that gcd1024 28 1024s 28t Solution 1024 36 2816 281 e1612 161124 12340 gcd102428 4 416 1gt12 416 1928 1x16 42 e128 36gt28 1gt28 53 Additional Proofs Lemma 531 Ifd h 6 2 and p is prime then p I ah ifdnd only if I d or p 17 Proof If p a then p I ah If p Jf a then gcdpd 1 and 3 st e Z such that 1 sp ta 7 sph tab Since p sph and p tab then p 17 El LECTURE 5 MAY 23 2007 16 Lemma 532 Ifalan Zandpisprimethenp u1gtgtunifpa10r plazororpan Proof By induction Hypothesis Sk above True V k 2 1 Base 51 p a p a if p a Step p Lil makil gt p a1akak1 Proved by lemma 531 Theorem 533 Any integer n 2 1 can be written as a product of unique primes Proof Uniqueness pi 11qu 112 q quot If p1 pi p22 piquot then p1 q q 11quot By Lemma 531 we can assume without loss of generality that p1 111 Since p1 and 111 are prime then p1 111 p32 p qizqquot Continuing with the application of Lemma 531 p2 qz pk qk El Lemma 534 V3 is irrational Proof Proof by contradiction Suppose V3 1 gcdm 1 M 6 Z 3 1 2 12 311 Lecture 6 May 25 2007 This section is waiting a reformatting Bijections and pigeonhole principle Useful for counting problems Sometimes easier to count a set if you map the set to something easier to count 61 Cartesian cross Product Cartesian Product For two sets A and B the Cartesian product or cross product of A and B is defined as A cross B a ha e A h e B Example 611 A 123B ah AcrossB 1 a 1 l7 2a 2 l7 3a 3 17 Example 612 lRCTOSSlR lR2 xyx y 6 1R Which is the Cartesian Plane The cross product can easily be defined in 11 sets Example 613 1Rquot lRm0sslRcross crosslR 62 Relations Relation For sets A and B any subset of ACr0ssB is said to be a relation from A to B By definition the cross product of A and B is a relation from A to B Example 621 1a a 17 is a relationfrom A to Bfrom Example 611 17 LECTURE 6 MAY 25 2007 18 63 Functions Mapping Function For any non empty sets A B a function or mapping from A to B is a relation from A to B such that every element of A occurs in exactly one ordered pair in the relation A function is written as f A gt B where A is the the domain and f B is the range Example 631 Is the relation in Example 621 a function No because 3 does not occur exactly once in every ordered pair 631 OnetoOneInjective OnetoOne Injective A function f A gt B is one to one if each element of B occurs at most once in the range of f A Corollary 631 If f A gt B is a onertorone function then A S B 632 Onto functions Onto Surjective A function f A gt B is onto if every element of B must occur exactly once in f A Corollary 632 A gt B is an ontofunction then A 2 B 64 Bijection Bijection A function f A gt B is a bijection if and only if it is both one to one and onto Example 641 The number ofsubsets of1 n 2quot Solution Let A subsets of 1 n and B binary sequences of length n 1 lt gt 100 13 lt gt 10100 LECTURE 6 MAY 25 2007 19 The numbers in the set on the left represent the positions in the binary sequence where a 1 exists Therefore this mapping is both one to one and onto so it is a bijection and A B Since B 2quot then A 2quot El 65 Pigeonhole Principle Pigeonhole Principle If in pigeons occupy n pigeonholes and in gt n then at least one pigeonhole is occupied by at least two pigeons Example 651 Among any 15 integers prove that there are at least two with the same remainder when divided by 14 Proof Let B be the possible remainders are the set given by n mod 14 which are 0 1 13 Because B 14 by the pigeonhole principle there must be at least two integers from any given set of 15 integers that have the same remainder when divided by 14 El Example 652 Let in 6 2 where in is odd Prove there exists a positive integer n such that in 2quot 1 Proof LetA 21 122 12m1 1 A 1n 1 Let B n mod in B in By the pigeonhole principle at least two elements of A have the same remainder when divided by in Given two integers e A Z 1 and 21 1 i lt in 21 1 21 1 so in 212quoti 1 Since in is odd then in Jf 2quot in 2quot1 1 El Lecture 7 May 30 2007 This day went into some really boring stuff I didn39t really feel the need to take notes De nition A u Bl AB A n Bl 71 Principle of Inclusion and Exclusion 711 Set Notation S is a set 5 11 C1 Ct are properties of elements of S N Ci Icil number of elements of S satisfying the property C NC1 C2 IC1 Czl number of elements of S satisfying the properties of both C1 and C2 This is stupid It39s clear that Ck is a subset but he won39t call it a subset Instead he calls them properties And instead of sticking to cardinality the ISI notation he creates this new notation of N S It just adds ab straction when you have multiple sets in the N 0 like N S T What is the relation between S and T Well if ST are independent then it39s just 0 Otherwise its IS 0 TI N 51 52 C number of elements of 5 not satisfying C1 0 C2 0 Ck Why does he do that but then throw around terms like union Test Friday June 8th 20 LECTURE 7 MAY 30 2007 72 June 1 2007 This lecture needs a reformatting The principle of inclusionexclusion should be easy 21 Lecture 8 June 4 2007 reformat me please 81 Derangements Continued Example 811 Given 1 2 n how many derangements are there Solution Let S arrangemntsof12 n C1 a 1 in the first position C2 a 2 in the second position Etc Nc 1cl So 51 1quotSn So I 51 Z NCi 1 i1 s2 Z Ncv a 2 Etc quot 1 kn N5152 Z k 10 82 Rook Polynomials De nition A Chessboard is a sub board of any grid 22 LECTURE 8 IUNE 4 2007 23 Rook Number Let C be a chessboard and k gt 0 be an integer Refine rkC the kth rank number of C as the number of ways to put k nontaking rooks on C Example 821 Let C 1 0 2 0 0 1 02 12 22 r0C 1 r1C6 r2C22228 r3C112 r4C0 Rook Polynomial rCx r0C r1Cx r2Cx2 rkCxk The rook polynomial of C 83 Mathematical De nition I39m a bit tired of these simplified explanations I looked up the definition for rook numbers on Mathworld and it makes a heck of a lot more sense Rook Number The rook numbers 7011 n of an mxn board are the number of subsets of size k such that no two elements have the same first or second coordinate It39s clear to me at least how this applies to what he is explaining 84 Computing Rook Polynomials Theorem 841 If a chessboard C consists of two disjoint subboards C1 and C2 then max CLXWCLX Solution Rule of products Duh Theorem 842 Let C be a chess board and select an element Let Cs be the set of squares in C that do not share a component with Let Ce be the set of C minus Then rCx xrCsx rCex Lecture 9 June 6 2007 Reformat Blah It39s cold 91 Arrangements with Forbidden Positions Example 911 Suppose there are three people R1 R2 R3 and R4 They are to be seated at five tables T1 T2 T3 T4 and T5 Each person is seated at his or her own table T1 does not want to be seated at T1 or T2 R2 does not want to be seated at T2 R3 does not want to be seated at T3 or T4 R4 does not want to be seated at T4 or T5 Solution Let S be the set of seating arrangements of R1 R4 at T1 T2 so that no two people are seated at the same table Let C1 be the property that R1 is seated at T1 or T2 Let C2 be the property that R2 is seated at T2 Let C the product of people and tables minus the forbidden person and table combinations N5152C3C71 2 S0 51 52 53 54 So P54 5 51 ZilNci Nc1 2 gt P43 Nc2 1 gt P43 Nc3 2 gt P43 Nc4 2 gt P43 24 LECTURE 9 IUNE 6 2007 25 51 2122gtP43 S2 ZikNCier 72C quot P3r2 53 r3CP2 1 S4 74CP10 To solve you can calculate rook polynomial rC 1 7x 16x2 13x3 3x4 Nc 1c 4 5 7gt4 15gt3 13gt2 3gt1 Lecture 10 June 13 2007 Reformat 101 Introduction to Generating Functions Generating functions are designed to help solve counting problems that are difficult to solve So far there have been two types of problems permu tations and combinations Similarly there will be two types of generating functions Ordinary generating functions solve arrangements Exponen tial generating functions solve permutations Example 1011 Find the number of distributions of twelve identical objects to four distinct boxes such that 4 S b0x1 S 6 3 S boxz b0x S 5 bays S 1 Example 1011 can be solved with case analysis but there would be many cases Furthermore if the upper restrictions were removed the solution to the example would be simple To solve we create a generating function Solution Let x be the number of objects in box i 12 3 4 x1x2x3X4 12 4 S X1 S 6 3 S X2 S 5 3 S X3 S 5 0 S X4 S 1 26 LECTURE 10 IUNE 13 2007 REFORMAT 27 To solve we write polynomials whose exponents are Values that the Variable can take gx x4 x5 x6x3 x4 x5x3 x4 x5x0 31 The coefficient of x12 in gx gives the answer to the problem By expanding the generating function or using case analysis you can find the coefficient Generating Function Let 010011012 n be a sequence of real numbers then fx d0d1x1d2x2dnxquot fx Z upi i0 Example 1012 The sequence of 1 1 1 has an ordinary generating function fxx0x1x2z i0 This form is not helpful so we should simplify it This series is d geometrix series with d common rdtio x With x lt 1 this series will converge to Example 1013 The sequence 0 0 hds d generating funcr tion fx 2361 1 xquot Theorem 1011 1 0 ni i i 1 xn n 1 x Proof The number of integer solutions to x1 x ixk 2 Dis The generating function for x1x2 x is fx x0x1xquotquot The coefficient of x139 is equal to the number of integer solutions when the sum of the series is i fltxgtz 1xl39 10 Example 1014 Find the coe icient ofx30 in x x2 x910 LECTURE 10 IUNE 13 2007 REFORMAT 28 Solution x x2 x910 9 x 13 xx10 1 172910 x 0 173010 9 1 Find the coefficient of x20 in 111915 1 00 Z oiolt 1gti1fx9igt 2 1 1 1139 i O coefficient of x20 2 101 1 1 1111 1 11 1212 1 21 102 Formulas for Series 1 11 1 xn71 quot Xi 1 x 10 1 xquot 10 Lecture 11 June 15 2007 Reformat 111 Partial Fraction Decomposition Example 1111 Find the coe icient ofx20 in l lixlix2 1 1 1 Solut10n1 m m m i xi i x Nowouse case0 analysis Fix the left term then select the right term ileft 20 iright 0 ileft 18 iright 1 ileft 16 iright 2 El Ieft Or iright There are 11 pairs so the coefficient of x20 is 11 Working with case analysis is easy when the power of x is small and fixed but if we were asked to find the coefficient of x201 or xquot it would be much harder In order to create an equation for the coefficient of a term you can use partial fractions Solution 2 In order to apply partial fractions the fraction needs to be decomposed into two parts 1 A BxC 17xlix2 17x 17x2 e numerator of the decomposed fractions need to be polynomials of lesser degrees The denominator of partial fractions cannot have common 29 LECTURE 11 IUNE 15 2007 REFORMAT 30 factors The original equation can be rewritten as 17x21x So the partial fraction decomposition is BxC A 17302 m A17x2BxC1ix 17x2 1x ACBC 2AXB xz 17x21x 1 ACBC 2AxBAx2 1AC gt1C B gt1 3B B gt B 0BC 2A gt0BC2B gtC 3B gtC g 0BA gtB A gtA 1 1 7 3 1 1m THHV Now expand the terms 1 i i x 3 0 i gig 1x 4 gnu The coefficient of x20 is 14120 3421 1420 11 This can be applied to the xquot case so that the coefficient of xquot is 141quot 3411 1 1411 112 Application of Partial Fractions Example 1121 Find the number of ways to take 100 objects from four distinct bins of an infinite number of identical objects such that there are an even number of objects taken from bins one and two and an odd number of objects taken from bins three and four Solution To solve this problem we will create a generating function for taking n objects from the four bins Next we have to set up a sequence Let an be the number of ways to take n objects from the four bins with the given restrictions The generating function gx is given by the following gx 2 u1xu2x2 uxquot gx x0 x2x4 2x1 33 35 2 30 11x22413xz2 M 28 gt LECTURE 11 IUNE 15 2007 REFORMAT 31 0 4 139 1 v 2 21 mag x xxzi 3ix2i g i0 3 The number of ways to select 100 objects from 4 bins with the given restrictions is 493 Lecture 12 May 18 2007 121 Exponential Generating Functions These are used to solve permutation problems De nition The exponential generating function for a sequence a0 a1 a2 an 00 0 1 2 n xk aox alx azx anx le fx 0 1 2 n k k0 Example 1211 Given a problem about permutations let an the answer to the 00 a xk problem Find the exponential generating function f x 2H anxk n1 Solution gt an n gt coefficient of xquot Example 1212 Find the number of ways to arrange 100 objects from three types such that an even number of objects are from type 1 and an odd number of objects are from type 2 Solution Let an denote the number of arrangements of n objects from three type such that an even number of objects are from type 1 and an odd number of objects are from type 2 fx 20 0 2 l 0 1 fx x gazes 6371 ex fx leer er 32 LECTURE 12 MAY 18 2007 33 fx Wquot w w 00 k 00 fx MN 2H gt H100 100 41013100x100 1100xlt100 01100 3100 1 122 More In nite Series Formulas Lecture 13 June 20 2007 131 The Summation Operation Example 1311 Given 010011012 find 5n a0 a1 a2 an Solution Now we have a new sequence 50 51 52 5n The generating function for the sequence is as follows 06 220 5quotxquot We can find f x 20 akxk which we can use to find gx gx 20a0 011 axquot 7 3 Proof Etoakxkxztoxk 50 the coefficient of xquot a0 a1 a2 an Proposition 1311 Let fx 210 ozka and gx 20a0 a1 axquot Then gx Example 1312 Find a compactformulafor 1 2 11 Solution Seton n 5n a0a1 a m mow 22M fxx2x23x3kxk 171x 1xx2xk Taking the derivative 34 LECTURE 13 JUNE 20 2007 35 HEW 12x3x2kxk 1 x2x3xkxk So fx 13 and M 13 Expanding gx we et gx x 20 3 x139 50 the coefficient of xquot gx 3114 71 Example 1313 Find the compactformulafor 1x2 2x3 3x4 n 1n Solution Let ak k 1k 5n a0a1a2 Lz71 1x22x3 n 1n fx 20 1ka f 536 12x2 23x3 1xx2xquot k 1kxk 1 HR 7x2 12x3x2kxk 1 1 2 3 12 23x k 1kxk 2 W 12x2 23x3 k 1kxk So fx 533 and M 5 M 2x2 20lt41i11gtxi Sm 2611 2a 2 W H i N R Example 1314 Find the compactformulafor Solution Letakz vzo Snza0a1an oo 1 k1 1 12 1 k fX Zk0mx TEX X mx 171x1xx2x Taking the integral of both sides llr 111 xxx7 3 3Ck n 7x Tf1 1 1 m fx x n 7x gx E xlix To find coefficients for xquot we would have to use Taylor series etc L L 4 Example 1315 Fmd the compact formula for M2 26 OHM Solution There is a simple trick to solve this problem easily Series LECTURE 13 JUNE 20 2007 36 Example 1316 Sn 13 23 n3 Let ak k3 x 2 210 ksxk 2 z kw H Multiply by x then take the derivative then multiply by x then take the derivative again 35 332 2 w 114f 2 W4 2 z W fx fx 4 2 x3 gx a m V gx x 4362 X3 20 551x1 Sn 5n1171 45n271 5n1371 Sn n13 4n12 n11 Usually we leave it alone at this point but since we know the formula for sum of cubes we know that it can be simpli ed S n3n2n1n 4n2n2nn71 n1nn71n72 7L 4l 41 41 5 quot111 3n 2 4n 2n 1 n 1n 2 5 quot11 6112 6n 5 mm 1120102 4 4 n Lecture 14 June 22 2007 Reformat This is the first lecture with the new professor Stephen Young 141 Recurrence Relations This will be the bulk of the test This section will be Learn by example for the most part The basic form of a recurrence relation is a function from one set to another Such as a N gt R where an 1 and and a0 5011 14012 45 etc Other examples bn22bn 1 n2b1 11121 521 35115 sin25nis n 2 0 We will focus on a few special recurrence relations and how to calculate them without having to recurse Example 1411 an 201111 301112 a0 1011 3 Find a general formfor an Solution The first step is to plug in some numbers and look for a pattern 10 I 1 H1 2 3 a2 2 gt 3 3 9 a3 2 273gt9 27 a4 3 812gt2781 37 LECTURE 14 IUNE 22 2007 REFORMAT 38 Noticing the pattern an may be equal to 3quot To see if it does we can prove it using induction hypothesis Pn 20114 30114 3quot V11 2 0 baseP0istme Assume Pk is true for all k stepPk 1 First Order The recurrence goes back one step For example an 110114 Linear The recurrence is limited to an Not other powers of an Homogeneous The recurrence does not depend on n Constant Coef cient All coefficients of the sequence terms are constant Example 1412 an 0114 11 2 0010 A Find a Closedform mctionfor an Solution a0 A 011ch azzczA H32C3A un A This can be proved using induction Example 1413 a 401010 511 2 0 Solution Trying to list the few outcomes for an is a headache 10 I 5 a1 5 a2 5 Another way to solve this without looking for a pattern is to reduce the original equation Let 7 01 so 170 as 125 law 2 ale 5a 2 5b 17 5 an 2 5 a 5 Example 1414 Show lim an 2 iflnan1 ln MMZO 211 2 0 Recurrence relations are similar to differential equations The same methods are used LECTURE 14 IUNE 22 2007 REFORMAT 39 Solution Let bn lnan so 170 1n2 bnl 1nan1 1n bn bn 1n2quot an elm gh ahgiquot 23quot 142 NonConstant Recurrence Relations Example 1421 pml gymn 2 2172 2 Solution p3 2372 633 1 p4261244 1 p5253gt122055 1 p6264gt203066 1 Pa n11 1 Can be proved using induction 143 Example 1431 and 2a 3a 1n 2 0a0 1a1 1 Solution a2 23 1 a3 32 1 H421 an 1quot Example 1432 Using the recurrence relation from the previous example find the general form for an with a0 2 a1 2 Solution a2 10 13 I H4 2 a5 2 823gt2616478242 a 3quot 1quot Inductive step LECTURE 14 IUNE 22 2007 REFORMAT am 22quot lt 1gtquotgt 33quot 11quot 1 2 3n 3 3711 24 3 1n1 37171 1n1 40 Lecture 15 June 25 2007 Reformat 151 Second Order Linear Constant Coef cient Recurrence Relations Remark If f n satisfies a linear homogeneous recurrence relation then Cf11 does as well for all C 6 1R Remark If f and g satisfy a linear homogeneous constant recurrence rela tion then so does f g Example 1511 H7111 40171 501111 Solution We make an initial guess that the solution for the recurrence relation is rquot So far the solutions have been in this form r7 4rquot 5r 1 1 rn 1r2 4r 5 0 50 r 5 l exclude 0 because it39s not interesting Now that we have Values for r we can find a solution for any given initial conditions Suppose a0 3 a1 9 an C15quot C2 lquot a0 C150 C2 10 C1 C2 3 a1 C151 C2 11 5C1 C2 9 Soul 2andczzl Example 1512 a gt SW1 b gt Sn 5111 For a general solution 41 LECTURE 15 IUNE 25 2007 REFORMAT 42 ar 1 brquot crn 1 rquot 1ar2 hr c 0 The ar2 hr c is called the characteristic polynomial of the recurrence relation The roots of the polynomial drives the behavior of the recurrence relation Example 1513 sn1 4s 5sn1s0 1s1 2 Example 1514 The characteristic polynomial is r2 4r 5 0 It s clear that there are complex roots here 5 is prime The roots are r 2 i i sn c12 iquot c22 iquot so c1 c2 1 s1 2c1 2c2 ic1 c2 So c1 c2 12 Remark Demarvway39s theorem fix name abi reie rcos6 isin6 which can be found using polar form So applying this to the problem at hand a bi reie a biquot rquotcosn6 i sinn6 Example 1515 c1a biquot c2a biquot r Va2 b2 6 arctanab 2 0 c1rquotcosn6 isinn6 czrquotcos n6 isin n6 c1rquotcosn6 i sinn6 szrquotcosn6 i sin n6 c1 c2rquot cosn6 c1 c2rquoti sinn6 So far we have covered two unique roots and two complex roots but what about the case when both roots are the same Example 1516 sn 4sn1 4sniz s0 1s1 2 Solution The Characteristic polynomial is r2 4r 4 0 or n 22 0 I39m going to show you what works and I wish I had a better intuition for why it works but I don39t It just works sn c12quot c2n2quot s0 c120 c2020 1 s1c12c22 1 1 Soclzlandczz E Lecture 16 June 27 2007 reformat 161 Review This is a quick review of Constant Coefficient Linear Homogeneous Re currence Relations This section generalizes the behavior of these forms of relations If r is multiplicity m it contributes a term in the form a0 mm aznz 0cm11nm 1rquot If r F are complex roots of multiplicity m then they contribute a term in the form a0 mm axnz am11nm 1rquot 30 3111 m11nm 1nm which is equal to C0 C111 Cm11nm 1rquot cosn6 id0 1111 dm11nm 1rquot sinn6 C e Z d e C 162 NonHomogeneous Recurrence Relations Example 1621 an un1 2quot a0 1 Solution an C1 1quot C22quot c1 1quot 022quot c1 1quot1 022 1 1 2quot 022quot c22n1 2 C2 2 C22 1 C2 23 so C1 13 Example 1622 an 201111 3quot a0 1 43 LECTURE 16 IUNE 27 2007 REFORMAT 44 Solution a0 1 H125 H2219 H3265 an c12quot c213quot C12quot c213quot 2c12r1 czsrl 3quot C2 2 23C2 1 C2 2 3 H0 C1203gt930 C13 1 gtC1 2 an 3nl 2nl Proposition 1621 Consider the linear constant coe icient nonrhornogeneous recurrence relation 20 cian1 f n If pn satis es fn and hn satis ed 20 ciawv 0 then pn hn satisfies f n Remark There are two things going on in a non homogeneous recurrence relation One part is homogeneous and the other is non homogeneous The non homogeneous part determines the behavior of the function Example 1623 an 9a1 20an2 3quot a0 a1 1 Solution First let39s just look at the homogeneous portion a gaze Solving for the characteristic polynomial we get r2 9r20r0r45 all c14quot c25quot Now we take a look at the non homogeneous portion the particular solution an c313quot We don39t use any initial conditions to solve for c3 instead we use the original recurrence relation Remember a3 satisfies the initial relation on its own c313 9c33quot 1 20c33quot 2 3quot C3 2 3C3 209C3 1 C3 2 Now we combine the particular and homogeneous solutions to get the final solution a an all LECTURE 16 IUNE 27 2007 REFORMAT 45 an C14quot C25quot 29 gt 3quot Using the initial condition C2 52 C1 5 Example 1624 an 3an1 3quot a0 1 Solution a5 3a 1 a5 3 a5 c2lt 3gtquot Cz3quot 3623 1 3quot C2 2 C2 We have a problem here In the same way that double roots mess up solutions when the homogeneous and particular solutions are the same there can be problems To solve we can multiply by n a C2n 3quot C2n 3quot 3C211 1 3quot 1 3quot C211C211 C21 C2 2 1 And then to combine the particular and homogeneous solutions and solving with the initial condition an quot3quot Ci3quot a0 0 30 C1 30 1 C1 2 1 an 3quot quot3quot 1621 Steps to solving a nonhomogeneous recurrence re lation H Find the associated homogeneous solution N Guess the form of the particular solution 03 Shift the particular solution out of the way of the homogeneous multiply by n so no terms in the particular and homogeneous solu tions overlap 4 Substitute particular solution into recurrence relation to find con stants LECTURE 16 IUNE 27 2007 REFORMAT 46 5 Sum the particular and homogeneous solutions and set it equal to the initial conditions to find remaining constants Lecture 17 June 29 2007 reformat 171 Combining Generating Functions and Re currence Relations Example 1711 Find the generating function for the following recurrence relur tion an 30114 uo l n 2 0 Solution unxquot 301714381 21 11x 2 21 311117135 Let f x 20 unxquot fx uo 3x 21 01143814 fx l 3x 20 uoxquot x 3xfx 1 f x 113x 203xquot Example 1712 Find the recurrence relation for the following recurrence relation an 0114 un2 n22quotu0 ul l n 2 0 Solution 22 unxquot 22 01711361 Z 0914quot Z n22nxquot Let f x 20 auxquot fx x 1 xfx 1 x2fx 39 2x fx xfx x2fx x 1 x 2 2quot 2x fx1 x x2 2x 1 MMquot 1 172x 14702 7 2X 1 2X fx 1 17x23 17372 lexixz libc2 47
Are you sure you want to buy this material for
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'