Numero Uno This subject has barely anything to do with computers, but it has been bugging me for over 30 years. It concerns some patterns I uncovered in Pascal's Triangle which I never committed to electronic text, until now. This may all be a waste of time, actually. I am not particularly gifted in math - I long ago found that any 'discoveries' I made while doodling with numbers always turned out to be either trivial or wrong. I'm a plugger, not a genius. Let's start with the number One and create a series: ``` 1 2 4 8 16 32 64 128 256 512 ... ``` Each new number is the previous one added to itself, in this case yielding the powers of 2 starting at 20. Now let's start with two Ones and create another series: ``` 1 1 2 3 5 8 13 21 34 55 89 144 ... ``` Now each new number is the sum of the previous two (with the exception of the Ones), and this yields the famous Fibonacci sequence. Then let's go with three Ones: ``` 1 1 1 2 3 4 6 9 13 19 28 41 60 ... ``` This is slightly more complicated to describe. Each new number is the sum of the previous one plus the "previous previous" one, that is, the "look-back" algorithm skips a number. More formally, the n-th term equals the sum of the (n - 1)-th and (n - 3)-th terms. Four Ones: ``` 1 1 1 1 2 3 4 5 7 10 14 19 26 ... ``` This time the algorithm skips two numbers. Now, the n-th term equals the sum of the (n - 1)-th and (n - 4)-th terms. Hey, we can do this forever, but what's the point? Well, ultimately I found the point was in the ratios of the succesive terms in the sequences. As the numbers in each series get larger, the ratios converge more and more accurately to specific irrational numbers: ``` 2.0 (except this one, which is a nice round natural integer) 1.618033... 1.465571... 1.380277... ``` And these are where it gets fun. Take the first irrational on the list, 1.618034, rounded. This is the famous Golden Ratio, of which you can find, according to Google, over 4 million pages containing all sorts of amazing facts. Or stay on this page and check out these facts: The G.R. is so famous it has it's own Greek letter, 'Phi' (Φ) assigned to it. Using that symbol, look at these equations: ``` Φ2 - Φ = 1 and Φ - 1/Φ = 1 ``` That is, Φ differs from both its square and its reciprocal by exactly one. The next irrational doesn't rate its own special symbol, so I'll just assign it the cliché 'X' (love the old standards): ``` X3 - X2 = 1 and X - 1/X2 = 1 ``` Once again we get differences of unity, although the exponents have moved up a degree. This time we'll make X = 1.380277..., and what do we get?: ``` X4 - X3 = 1 and X - 1/X3 = 1 ``` Hmmm. Is a pattern showing up? To generalize, let's call these ratios p-ratios. That way we can give our X a subscript. For example, When X = 2, we'll call that version of X, X0. Then Φ will equal X1, and so on. Now we can create general equations for all the p-ratios: ``` XpP+1 - Xpp = 1 (1) Xp - 1/Xpp = 1 (2) ``` Ah yes, but do they work for the ratios of higher sequences? You betcha! Back in 1980 or so, when I was more patient (or more obsessive), I spent an afternoon on my calculator deriving ratios for all the P subscripts ("p-scripts") up through 16. And then threw in 19, 22, and 28 for good measure. "However," you say, "that's not a real proof." "But," I answer, "I'm not a real mathematician." Still, if it will make you happy, you can find the algebraic derivations of these guys at: Generalized Golden Sections, which is the deepest exploration of this subject that I found online. They go on to derive all sorts of mathematical borscht (you can also read their site in Russian) that is pretty much over my head. And yet ... a part of me thinks that they and others miss the main point. And what is that point? Look again at the equations. There are Ones falling out all over the place, and what I see online basically treats this fact as an amusing coincidence. How the Hell ... Am I missing something here? These ratios are real roots of high degree polynomials, derived from additive series. Seriously, rewrite the first equation in a more standard format: ``` XpP+1 - Xpp - 1 = 0 ``` Now imagine P being equal to a thousand, a million, a billion, a googol. These are ridiculously high degree polynomials, yet we have a plodding, counting way to focus in on one of their roots. Admittedly, these polynomials are very sparse (by far, most of the terms are 0), but still, find me another algorithm to solve them when P is very very high. Well, maybe there are several. For the third time: I'm not a mathematician. Maybe I've been seduced by coincidences after all. "Oooh, the magic of numbers!" Maybe there's something so trivial or obvious going on here that I will end up taking this page down in embarassment when it's pointed out to me. I guess perhaps my biggest failing when it comes to studying mathematics is that I tend to ask "Why?" I get caught up in, "Why does this pattern show up?" "What does it all mean?" Maybe those are not the kinds of inquires that get practical work done? If you goofed around enough with brute force approaches, I would suppose you could find whole collections of irrationals that produced any specific gap between large pairs of powers. Want to find some series that produces   XpP+1 - Xpp = PI?   Or,  = your telephone number ? They may be out there to be discovered. But could you find an integer counting series that leads to them? Hmm, what if you could? Hmmmm ... Counting has always grabbed my attention as the most fundamental part of math. I guess the number theorists agree with me on that. There's something about Unity, One, that is perhaps the most basic intellectual building block there is (although Zero may trump it). Sometimes even multiplication and division seem kind of like cheating, in a way. Yes, I suppose that takes my opinion of what's fundamental a little too far. And truthfully, by that standard, this p-ratio algorithm I'm writing about is ultimately not totally a counting system, because the final step is to divide, in order to produce the ratio. Of course, multiplication is merely repeated addition. And raising to a power is therefore repeated addition on steroids. P-script 0 is just adding powers of 2 to themselves, and nobody makes a big deal about that. Similarly, the series: ``` 1 3 9 27 81 243 729 ... ``` is the powers of 3, derived by adding each number to itself 3 times instead of 2 times. We can apply the look-back system, adding three previous numbers this time, and come up with a new list: ``` 1 1 1 3 5 9 17 31 57 105 193 355 653 1201 2209 ... ``` which quickly reaches the ratio 1.8392867, rounded. No doubt this is a new astounding number with all sorts of unusual properties somebody can explore. But not me. It is time for me to get back to something practical. Still, at least I've gotten a thirty year old monkey off my back   ...   Oh, did you think I was going to stop here?   Haw!   Never! Pascal's Angles I took the term p-ratios from the link above. These sequences can all be found within Pascal's Triangle: ``` 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 ... ``` which is best known for describing the expansion of binomial coefficients of yes, polynomials. For example: ``` (a + b) * (a + b) = 1a2 + 2ab + 1b2 ``` where the coefficients 1,2,1 can then be found on the third row of the triangle. Then: ``` (a + b)3 = 1a3 + 3a2b + 3ab2 + 1b3 ``` the coefficients 1,3,3,1 can then be found on the fourth row of the triangle, and so on. If we add each row across, we get the sequence 1, 2, 4, 8, 16 ..., which is p-script 0. The other p-scripts can also be found by adding the Pascal numbers of different slopes. This is clearer if we tilt the triangle, left-justify it: ``` 1 1 1 1 1 ... 1 2 3 4 5 ... 1 3 6 10 15 ... 1 4 10 20 35 ... 1 5 15 35 70 ... ... ``` And then start shifting each line to the right: ``` 1 1 1 1 1 1 ... 1 2 3 4 5 ... 1 3 6 10 ... 1 4 10 ... 1 5 ... 1 ... ... ``` Now we add down to get the 1, 2, 4, 8, 16, 32 ... binary powers. Shift again: ``` 1 1 1 1 1 1 1 1 1 1 ... 1 2 3 4 5 6 7 8 ... 1 3 6 10 15 21 ... 1 4 10 20 ... 1 5 ... ... ``` And if we add down, we get the 1, 1, 2, 3, 5, 8, 13 ... Fibonacci sequence. Shift once more and we can add down to get the X2 sequence: ``` 1 1 1 1 1 1 1 1 1 1 1 1 ... 1 2 3 4 5 6 7 8 9 ... 1 3 6 10 15 21 ... 1 4 10 ... ... ``` And so on to derive all the p-ratios. We can keep going higher and higher and find all of them in the triangle. Infinity Minus One Here's an interesting question: can we go lower? Is there such a thing as p-script -1? Go back to our original left-justified triangle: ``` 1 1 1 1 1 ... 1 2 3 4 5 ... 1 3 6 10 15 ... 1 4 10 20 35 ... 1 5 15 35 70 ... ... ``` What happens now when we add down? Everything adds to infinity, bigger and bigger infinities ... except according to one of my very favorite mathematicians, Georg Cantor, they aren't bigger and bigger, they are all the same size! Go ahead and disagree with me, but if you take on Georg you're taking on a real mathematician for a change. We can take the first general equation for the p-ratios: ``` XpP+1 - Xpp = 1 ``` Multiply both sides by 1 / Xpp, and get: ``` Xp - 1 = 1 / Xpp ``` This holds true for all the non-negative p-scripts (this is actually a reformulation of the second general equation) Go ahead and plug some of the numbers in if you have a calculator handy. Does it hold for p-script -1? ``` X-1 - 1 = 1 / X-1-1 ? ``` Well, what IS p-script -1? Using the sums of the Pascal columns, is it the ratio of infinity to infinity, or "one"? ``` 1 - 1 = 1 / 1-1 ? ``` or: ``` 1 - 1 = 1/1/1 ? ``` or: ``` 0 ≠ 1 [ oops, guess not ] ``` which goes to show that infinity over infinity is undefined, not One. However, let's not give up on  Xp - 1 = 1 / Xpp  just yet. Let's go the other direction and see what we get with p-script = infinity. Let's get our definitions right this time and admit that  X∞  would also be undefined. Infinity is uncountable, by definition. Better to say that P gets bigger and bigger as it 'approaches' infinity (→∞): ``` XBIG - 1 = 1 / XBIGBIG ``` Keep in mind that as the p-script gets bigger, the p-ratio gets smaller, ever nearer to One. Meanwhile, the value of the p-ratio raised to the P power gets bigger. So as it does approach infinity, the equation still works. Both general equations still work. As far as deriving the ratios from Pascal's Triangle, it means we must keep staggering the rows more and more to the right. It also means we can't get away with summing up that squared off triangle. But it was fun to try. The whole infinity concept is pretty sneaky, actually. If you did go and check out the algebraic derivation of the general equations, you saw they used the series expansion thing. Most of the times when you see a bunch of multiplications in both a numerator and a denominator, and they each have a "3-dot" embedded in them, the next thing you know they'll be cancelling out all the like terms ("as n goes to infinity"), leaving two terms left: what they're looking for, and one term "that is so small it can be thrown away." Infinity minus One! Well, actually Infinity minus something infinitely tiny. Cannot really argue, though. That trick is an important part of mathematics, which underlies modern science, which is the basis for all the technology we've grown so comfortable with. Let's just call it "clever," not "sneaky." For a different take on the subject of infinity, there's a short page at: Discrete Models. One last note about that last equation we looked at. I find reciprocals almost as fascinating as Unity. Think about it: the whole infinite range of all numbers is reflected back within the interval between Zero and One. It tempts me to ask "why" some more, or at least "how?" "Oooh, mysterious!" Some random notes: The golden ratio Φ is a continued fraction of a bunch of Ones, often written compactly as: ``` [1; 1, 1, 1, 1, 1, 1, ...] ``` It is also a continued square root (infinite surd) of ... a bunch of Ones. As with continued fractions, there's a "One plus" under each radical sign: (√1 + √(1 + √ ...)). Cassini's Identity says that if you square any Fibonacci number, the result will always differ from the sum of its neighbors on either side, by One. Sometimes it will be larger by 1, sometimes smaller. Here's a series where applying the Cassini algorithm apparently always yields a difference of 5: ``` 1 3 4 7 11 18 29 47 76 123 199 322 521 843 1364 2207 3571 ... ``` Where does it come from? As you keep raising Φ to ever increasing powers, they become ever closer to a nearby whole number. This series is the list of those numbers, after rounding. Actually, the first number, 1, cheats as Φ = 1.6180334 yet it is rounded down. Now, that's pretty sloppy. Is there a better way to round them? Sure there is. Remember the equation for p-script 1: ``` Φ2 - Φ = 1 ``` With the quadradic formula Φ can be solved for its positive root: ``` Φ = (1 + √5) / 2 ``` It also has a negative root: ``` (1 - √5) / 2 ``` which ends up equaling -.618034, or -1 / Φ. THERE's the rounding factor! Each Φ-power misses the whole number it's associated with by the negative root raised to the same power. Don't want to have to keep adding all those successive numbers to each other to get to the n-th Fibonacci number? Don't have to. There's Binet's Formula that will yield whatever n-th Fibby you might be looking for. It makes use of both roots of the Φ-quadradic. Here is an interesting sequence in a similar vein from Jim Loy's page on the golden ratio (no, he's no relation to me that I know of): ø2=ø+1 ø3=2ø+1 ø4=3ø+2 ø5=5ø+3 ø6=8ø+5 ø7=13ø+8 . . . øn=F(n)ø+F(n-1) "Notice the Fibonacci Numbers on the right side of each equal sign. F(n) is the nth Fibonacci number." Darned if somebody didn't come up with negafibonacci numbers, which can be computed by the equation: ``` FIB-n = (-1)n+1 * FIBn ``` derived from "the re-arranged recurrence relation": ``` FIBn-2 = FIBn - FIBn-1 ``` Thus the Fibonacci sequence can extend in both directions: ``` ... -21 13 -8 5 -3 2 -1 1 0 1 1 2 3 5 8 13 21 ... ``` Can the other sequences I started this essay out with also be extended? Sometime when I have time ... or you have time? One more ... 1/89 = 0.011235955056179... See the first few digits to the right of the decimal point? They look like a certain sequence, no? Indeed they are, and they actually continue perfectly, it's just that the multi-digit F-numbers quickly overlap and get in each other's way. Eventually, carries also come into play: ``` .01 .001 .0002 .00003 .000005 .0000008 .00000013 .000000021 .0000000034 .00000000055 + .000000000089... ------------------ 0.011235955056... ``` There's a proof that these truly do add up to 1/89 on the ThinkQuest site. They make use of a slightly different application of that sneaky, er, clever infinite series trick we discussed above. On the WolframAlpha site, you can enter the fraction and it will tell you that this ultimately ends being a repeating decimal of period 44, starting at the first 1. This is rather remarkable, yes? Does this hold true for number bases other than ten? Does the repeating decimal make 1/89 a self-similar fractal? Finally, since I went to the trouble of computing them, there's a list of the first 32 P-ratios, rounded: ``` Ratio 0 = 2.000000000000000000 Ratio 1 = 1.618033988749894902 Ratio 2 = 1.465571231876767966 Ratio 3 = 1.380277569097614121 Ratio 4 = 1.324717957244746058 Ratio 5 = 1.285199033245349343 Ratio 6 = 1.255422871076846469 Ratio 7 = 1.232054631428572300 Ratio 8 = 1.213149723059639973 Ratio 9 = 1.197491433551680862 Ratio 10 = 1.184276322350893862 Ratio 11 = 1.172950750023980193 Ratio 12 = 1.163119790669204345 Ratio 13 = 1.154493550709056571 Ratio 14 = 1.146854042199506818 Ratio 15 = 1.140033937477004988 Ratio 16 = 1.133902490334837365 Ratio 17 = 1.128355939691602972 Ratio 18 = 1.123310806246326621 Ratio 19 = 1.118699108052225943 Ratio 20 = 1.114464879953438237 Ratio 21 = 1.110561598122310256 Ratio 22 = 1.106950245016882217 Ratio 23 = 1.103597835338253841 Ratio 24 = 1.100476279034370286 Ratio 25 = 1.097561494232327517 Ratio 26 = 1.094832707905311953 Ratio 27 = 1.092271899234358079 Ratio 28 = 1.089863352616994740 Ratio 29 = 1.087593295779058389 Ratio 30 = 1.085449604556999015 Ratio 31 = 1.083421560363417857 ``` Unlike three decades ago, when I punched my way through one of the general equations to arrive at the values, This time I wrote a program and used my handy C compiler to perform the actual additions on the members of the sequences. For higher ratios, these converge painfully slowly, but since I had floating point exponentiation available up to 10308, I simply broke off the additions at 307 and divided the two most recent huge P-script numbers. I'm just clever enough to be dangerous! Acknowlegements: A shout out to my perhaps long lost distant cousin Jim Loy. As I did research for this blog, I ran across his mathematics pages and snuck a look at the source code. I found out you can write math equations directly in HTML. Actually, I had known about super- and sub-scripts, but later had forgotten. But Jim's code showed me that HTML supports all sorts of standard math symbols. A good list is on a Wikipedia Help page, just above the section "Pros of HTML," which you can jump to from the Contents box. Without this fortitious discovery, this page would have ended up with cheesy graphics like my Cordic Discussion. Thanks, Jim! The Golden Museum site delves deeply into using Φ as a new positional number base. If you want to read about it, you'll find their English language home page is set up into frames, which I hate. So I hacked their code to display the mathematics table of contents on a full screen: Mathematics of Harmony. One of their main conclusions, about the "phinary" number base, is in my opinion boiled down more clearly on Wikipedia's Golden ratio base. To quote: "Any non-negative real number can be uniquely represented as a base-phi numeral using only the digits 0 and 1, and avoiding the digit sequence "11" ..." A somewhat similar page covers the Fibonacci code, a universal, self-synchronizing data compression code. It uses "11" as the "stop" flag for each code. Is Wikipedia the best thing on the Internet or what? It is one of the very few online resources I bother to pay for. Join me in donating?

Flexible System Architecture    —   Home