115-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)21 + 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) = 2S1 2 . . . . . . . . n1 2 . . . . . . . . n1 2 . . . . . . . . n1 2 . . . . . . . . nn . . . . . . . 2 1n . . . . . . . 2 1n . . . . . . . 2 1n . . . . . . . 2 1nthTriangular Number∆n= 1 + 2 + 3 + . . . + n-1 + n= n(n+1)/2nthSquare Numbern= n2= ∆n+ ∆n-13Breaking a square up in a new way Breaking a square up in a new way1Breaking a square up in a new way1 + 3Breaking a square up in a new way1 + 3 + 54Breaking a square up in a new way1 + 3 + 5 + 7Breaking a square up in a new way1 + 3 + 5 + 7 + 91 + 3 + 5 + 7 + 9 = 52Breaking a square up in a new wayPythagorasThe sum of the first n odd numbers is n25Here is an alternative dot proof of the same sum…. n= ∆n+ ∆n-1= n2nthSquare Numbern= ∆n+ ∆n-1= n2nthSquare Numbern= ∆n+ ∆n-1nthSquare Number6n= ∆n+ ∆n-1= Sum of first n odd numbersnthSquare NumberCheck the next one out… ∆∆∆∆nnnn∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)2∆∆∆∆nnnn----1111∆∆∆∆nnnn----1111∆∆∆∆nnnn∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)27∆∆∆∆nnnn----1111∆∆∆∆nnnn----1111??∆∆∆∆nnnn∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)2∆∆∆∆nnnn----1111∆∆∆∆nnnn----1111nn∆∆∆∆nnnn∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)2∆∆∆∆nnnn----1111∆∆∆∆nnnn----1111nn∆∆∆∆nnnn∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)2∆∆∆∆nnnn----1111∆∆∆∆nnnn----1111nn∆∆∆∆nnnn∆∆∆∆nnnn(∆∆∆∆nnnn----1111)2n∆∆∆∆nnnn----1111n∆∆∆∆nnnnArea of square = (∆∆∆∆nnnn)2= (∆n-1)2+ n∆n-1+ n∆n= (∆n-1)2+ n(∆n-1+ ∆n)= (∆n-1)2+ n(n)= (∆n-1)2+ n38(∆∆∆∆nnnn)2 = n3+ (∆∆∆∆nnnn----1111)2= n3+ (n-1)3+ (∆∆∆∆nnnn----2222)2= n3+ (n-1)3+ (n-2)3+ (∆∆∆∆nnnn----3333)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!91 + X1+ X2+ X3+ … + Xn-2+ Xn-1=X - 1Xn – 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-1an-2… a1a0 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-1Xn-1+ an-2Xn-2+ . . . + a0X010Sumerian-Babylonian: 10, 60, 360Egyptians: 3, 7, 10, 60Maya: 20Africans: 5, 10French: 10, 20English: 10, 12, 20Bases In Different CulturesBASE X Representation S = ( an-1an-2… a1a0 )Xrepresents the number:an-1Xn-1+ an-2Xn-2+ . . . + a0X0Largest 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-1is 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-1is uniquely represented by an n-“digit” number in base X11n 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”12Here’s What You Need to Know…Unary and BinaryTriangular 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