In my previous post, we found an answer to the question:
What’s the 99th digit to the right of the decimal point in the decimal expansion of ?
However, the solution depended on having the clever idea to add . But there are other ways to come to similar conclusions, and in fact this is not the way I originally solved it.
The first thing I did when attacking the problem was to work out some small powers of by hand:
and so on. It quickly becomes clear (if you have not already seen this kind of thing before) that will always be of the form . Let’s define and to be the coefficients of the th power of , that is, . Now the natural question is to wonder what, if anything, can we say about the coefficients and ? Quite a lot, as it turns out!
We can start by working out what happens when we multiply by another copy of :
But by definition, so this means that and . As for base cases, we also know that , so and . From this point it is easy to quickly make a table of some of the values of and :
Each entry in the column is the sum of the and from the previous row; each is the sum of the previous and twice the previous . You might enjoy playing around with these sequences to see if you notice any patterns. It turns out that there is an equivalent way to define the and separately, such that each only depends on previous values of , and likewise each only depends on previous . I’ll explain how to do that next time, but leave it as a challenge for you in the meantime!
Looks like for each of the coefficients, there is the same pattern: twice the previous coefficient plus the coefficient before that one. For example, for n = 6, 99 = 2(41) + 17, and 70 = 2(29) + 12
Right! Can you prove it? (Without peeking at Thibault’s comment below? =)
[Of course don’t read my comment if you don’t wanna spoil yourself]
We can observe that and (each is the sum of twice the previous one, and the one two rows above it – and the same pattern goes for the ).
It is possible to prove it by induction, but let us do it another simple way:
– notice that .
– it follows that , if we multiply both sides of the equality by .
– by definition of and , we get . Now, since the decomposition where and are integers is unique (thanks to ‘s irrationality), we must have that and .
*, oops !
Oh, very nice! I had a different proof, but I knew there had to be something like this.
I think I’ve seen those numbers before…
Yes, are the continued fraction convergents to .
THANK YOU FOR THAT CLEVER SOLUTION TO (1 + SQRT(2))^500.
Re Irrational numbers, like SQRT(2), pi, e, etc:
“Are all irrational numbers equally random ?” I ran 1000 digits of SQRT(2) through an FFT generator and the result seemed like pure, random noise. What feature of the number system guarantees such outcomes ? I don’t get it. And finally, why not use such irrational random numbers as keys to encryption algorithims ?
“Are all irrational numbers equally random?” — you would have to define what you mean by random, but for any reasonable definition the answer is definitely no. For example, 0.1234567891011121314151617… is irrational, but its sequence of decimal digits is very nonrandom. In general, deciding whether the digits of some particular number are “random” according to some definition (e.g. do all digits occur equally often? or all sequences of digits?) is a very hard question. For example, we do not actually know of a concrete example of a “normal” number (one whose digits are equally distributed in every base) even though we know that *almost all* real numbers must be normal!
As for why not use the digits of irrational numbers as encryption keys, the answer is that although they may be “random” in one sense, they are very non-random in another sense: they are completely, deterministically predictable. It’s like the difference between using randomly chosen letters as a key (which would be very hard to guess) and using letters from a widely published book containing random letters: the letters may appear random, but once I realize you are using letters from the widely known book, I can decrypt all your secrets. It is much easier to guess which book you are using than to guess the particular random letters you have chosen.