Sequences and SummationsDefinitionsSequencesSequence examplesGeometric vs. arithmetic sequencesFibonacci sequenceFibonacci sequence in natureReproducing rabbitsSlide 9Slide 10Slide 11Slide 12Slide 13The Golden RatioSlide 15Determining the sequence formulaSlide 17Slide 18OEIS: Online Encyclopedia of Integer SequencesUseful sequencesQuick surveyGeeky TattoosSummationsEvaluating sequencesSlide 25Summation of a geometric seriesProof of last slideDouble summationsUseful summation formulaeAll your base are belong to usCardinalitySlide 33More definitionsShowing a set is countably infiniteShowing ordered pairs of integers are countably infiniteSlide 37Slide 38Slide 39Today’s demotivators11Sequences and Sequences and SummationsSummationsCS/APMA 202CS/APMA 202Rosen section 3.2Rosen section 3.2Aaron BloomfieldAaron Bloomfield22 DefinitionsDefinitionsSequence: an ordered list of elementsSequence: an ordered list of elementsLike a set, but:Like a set, but:Elements can be duplicatedElements can be duplicatedElements are orderedElements are ordered33 SequencesSequencesA sequence is a function from a subset of A sequence is a function from a subset of ZZ to a set S to a set SUsually from the positive or non-negative intsUsually from the positive or non-negative intsaann is the image of is the image of nnaann is a term in the sequence is a term in the sequence{{aann} means the entire sequence} means the entire sequenceThe same notation as sets!The same notation as sets!44 Sequence examplesSequence examplesaann = 3 = 3nnThe terms in the sequence are The terms in the sequence are aa11, , aa22, , aa33, …, …The sequence {The sequence {aann} is { 3, 6, 9, 12, … }} is { 3, 6, 9, 12, … }bbnn = 2 = 2nnThe terms in the sequence are The terms in the sequence are bb11, , bb22, , bb33, …, …The sequence {The sequence {bbnn} is { 2, 4, 8, 16, 32, … }} is { 2, 4, 8, 16, 32, … }Note that sequences are indexed from 1Note that sequences are indexed from 1Not in all other textbooks, though!Not in all other textbooks, though!55 Geometric vs. arithmetic Geometric vs. arithmetic sequencessequencesThe difference is in how they growThe difference is in how they growArithmetic sequences increase by a constant Arithmetic sequences increase by a constant amountamountaann = 3 = 3nnThe sequence {The sequence {aann} is { 3, 6, 9, 12, … }} is { 3, 6, 9, 12, … }Each number is 3 more than the lastEach number is 3 more than the lastOf the form: Of the form: ff((xx) = ) = dxdx + + aaGeometric sequences increase by a constant Geometric sequences increase by a constant factorfactorbbnn = 2 = 2nnThe sequence {The sequence {bbnn} is { 2, 4, 8, 16, 32, … }} is { 2, 4, 8, 16, 32, … }Each number is twice the previousEach number is twice the previousOf the form: Of the form: ff((xx) = ) = ararxx66 Fibonacci sequenceFibonacci sequenceSequences can be neither geometric or Sequences can be neither geometric or arithmeticarithmeticFFnn = F = Fn-1n-1 + F + Fn-2n-2, where the first two terms are 1, where the first two terms are 1Alternative, Alternative, FF((nn) = ) = FF((nn-1) + -1) + FF((nn-2)-2)Each term is the sum of the previous two termsEach term is the sum of the previous two termsSequence: { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … }Sequence: { 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … }This is the Fibonacci sequenceThis is the Fibonacci sequenceFull formula:Full formula:   nnnnF255151)(77 Fibonacci sequence in natureFibonacci sequence in nature138532188 Reproducing rabbitsReproducing rabbitsYou have one pair of rabbits on an islandYou have one pair of rabbits on an islandThe rabbits repeat the following:The rabbits repeat the following:Get pregnant one monthGet pregnant one monthGive birth (to another pair) the next monthGive birth (to another pair) the next monthThis process repeats indefinitely (no deaths)This process repeats indefinitely (no deaths)Rabbits get pregnant the month they are bornRabbits get pregnant the month they are bornHow many rabbits are there after 10 How many rabbits are there after 10 months?months?99 Reproducing rabbitsReproducing rabbitsFirst month: 1 pairFirst month: 1 pairThe original pairThe original pairSecond month: 1 pairSecond month: 1 pairThe original (and now pregnant) pairThe original (and now pregnant) pairThird month: 2 pairsThird month: 2 pairsThe child pair (which is pregnant) and the parent pair The child pair (which is pregnant) and the parent pair (recovering)(recovering)Fourth month: 3 pairsFourth month: 3 pairs““Grandchildren”: Children from the baby pair (now pregnant)Grandchildren”: Children from the baby pair (now pregnant)Child pair (recovering)Child pair (recovering)Parent pair (pregnant)Parent pair (pregnant)Fifth month: 5 pairsFifth month: 5 pairsBoth the grandchildren and the parents reproducedBoth the grandchildren and the parents reproduced3 pairs are pregnant (child and the two new born rabbits)3 pairs are pregnant (child and the two new born rabbits)1010 Reproducing rabbitsReproducing rabbitsSixth month: 8 pairsSixth month: 8 pairsAll 3 new rabbit pairs are pregnant, as well as those not All 3 new rabbit pairs are pregnant, as well as those not pregnant in the last month (2)pregnant in the last month (2)Seventh month: 13 pairsSeventh month: 13 pairsAll 5 new rabbit pairs are pregnant, as well as those not All 5 new rabbit pairs are pregnant, as well as those not pregnant in the last month (3)pregnant in the last month (3)Eighth month: 21 pairsEighth month: 21 pairsAll 8 new rabbit pairs are pregnant, as well as those not All 8 new rabbit pairs are pregnant, as well as those not pregnant in the last month (5)pregnant in the last month (5)Ninth month: 34 pairsNinth month: 34 pairsAll 13 new rabbit pairs are pregnant, as well as those not All 13 new rabbit pairs are pregnant, as well as those not pregnant in the last month (8)pregnant in the last month (8)Tenth month: 55 pairsTenth month: 55 pairsAll 21 new rabbit pairs are pregnant, as well as those not All 21 new rabbit pairs are pregnant, as well as those not pregnant in the last month (13)pregnant in the last month (13)1111 Reproducing rabbitsReproducing rabbitsNote the sequence:Note the sequence:{