Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 4515-251Great Theoretical Ideas in Computer ScienceLecture 5 (September 11, 2007)Ancient Wisdom: Unary and Binary1234Prehistoric UnaryConsider the problem of finding a formula for the sum of the first n numbersYou already used induction to verify that the answer is ½n(n+1)1 + 2 3 n-1 n S+ + … + + =1+2…n-1n S++n-2++ =n+1+n+1…n+1n+1 2S++n+1++ =n(n+1) = 2SS = n(n+1)21 + 2 3 n-1 n S+ + … + + =1+2…n-1n S++n-2++ =n(n+1) = 2S 1 2 . . . . . . . . n n . . . . . . . 2 1There are n(n+1) dots in the grid!S = n(n+1)2nth Triangular Numbern = 1 + 2 + 3 + . . . + n-1 + n= n(n+1)/2nth Square Numbern = n2= n + n-1Breaking a square up in a new wayBreaking a square up in a new way 1Breaking a square up in a new way 1 + 3Breaking a square up in a new way 1 + 3 + 5Breaking a square up in a new way 1 + 3 + 5 + 7Breaking a square up in a new way 1 + 3 + 5 + 7 + 91 + 3 + 5 + 7 + 9 = 52Breaking a square up in a new wayPythagoras The sum of the first n odd numbers is n2Here is an alternative dot proof of the same sum….n = n + n-1 = n2nth Square Numbern = n + n-1 = n2nth Square Numbern = n + n-1 nth Square Numbern = n + n-1 = Sum of first n odd numbersnth Square NumberCheck the next one out…nnArea of square = (n)2n-1n-1nnArea of square = (n)2n-1n-1??nnArea of square = (n)2n-1n-1nnnnArea of square = (n)2n-1n-1nnnnArea of square = (n)2n-1n-1nnnn(n-1)2nn-1nnArea of square = (n)2= (n-1)2 + nn-1 + nn= (n-1)2 + n(n-1 + n)= (n-1)2 + n(n)= (n-1)2 + n3(n)2 = n3 + (n-1)2= n3 + (n-1)3 + (n-2)2= n3 + (n-1)3 + (n-2)3 + (n-3)2= n3 + (n-1)3 + (n-2)3 + … + 13(n)2 = 13 + 23 + 33 + … + n3 = [ n(n+1)/2 ]2Can you find a formula for the sum of the first n squares? Babylonians needed this sum to compute the number of blocks in their pyramidsA man has 7 houses,Each house contains 7 cats,Each cat has killed 7 mice,Each mouse had eaten 7 ears of spelt,Each ear had 7 grains on it.What is the total of all of these?Sum of powers of 7Rhind PapyrusScribe Ahmes was Martin Gardener of his day!1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1We’ll use this fundamental sum again and again:The Geometric SeriesA Frequently Arising Calculation(X-1) ( 1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 )X1 + X2 + X3 + … + Xn-1 + Xn- 1 - X1 - X2 - X3 - … - Xn-2 - Xn-1= Xn - 1= 1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1(when x ≠ 1)1 + X1 + X2 + X3 + … + Xn-2 + Xn-1 = X - 1 Xn – 1(when x ≠ 1)1 + 21 +22 + 23 + … + 2n-1 = 2n -1Geometric Series for X=2BASE X RepresentationS = an-1 an-2 … a1 a0 represents the number: Base 2 [Binary Notation]101 represents:1 (2)2 + 0 (21) + 1 (20)Base 7015 represents:0 (7)2 + 1 (71) + 5 (70)==an-1 Xn-1 + an-2 Xn-2 + . . . + a0 X0Sumerian-Babylonian: 10, 60, 360Egyptians: 3, 7, 10, 60Maya: 20Africans: 5, 10French: 10, 20English: 10, 12, 20Bases In Different CulturesBASE X Representation S = ( an-1 an-2 … a1 a0 )X represents the number:an-1 Xn-1 + an-2 Xn-2 + . . . + a0 X0Largest number representable in base-X with n “digits”= (X-1 X-1 X-1 X-1 X-1 … X-1)X= (X-1)(Xn-1 + Xn-2 + . . . + X0)= (Xn – 1)k uses log2k + 1 digits in base 2Fundamental Theorem For BinaryEach of the numbers from 0 to 2n-1 is uniquely represented by an n-bit number in binaryk uses logXk + 1 digits in base XFundamental Theorem For Base-XEach of the numbers from 0 to Xn-1 is uniquely represented by an n-“digit” number in base Xn has length n in unary, but has length log2n + 1 in binaryUnary is exponentially longer than binaryOther Representations:Egyptian Base 3We can prove a unique representation theoremExample: 1 -1 -1 = 9 - 3 - 1 = 5Here is a strange new one: Egyptian Base 3 uses -1, 0, 1Conventional Base 3: Each digit can be 0, 1, or 2How could this be Egyptian? Historically, negative numbers first appear in the writings of the Hindu mathematician Brahmagupta (628 AD)One weight for each power of 3 Left = “negative”. Right = “positive”Here’s What You Need to Know…Unary and Binary Triangular NumbersDot proofs(1+x+x2 + … + xn-1) = (xn -1)/(x-1)Base-X representationsk uses log2k + 1 = log2 (k+1) digits in base
View Full Document