The curious powers of 1 + sqrt 2: recurrences

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 (1 + \sqrt 2)^{500}?

However, the solution depended on having the clever idea to add (1 + \sqrt 2)^n + (1 - \sqrt 2)^n. 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 1 + \sqrt 2 by hand:

\displaystyle \begin{array}{rcl} (1 + \sqrt 2)^2 &=& 1 + 2 \sqrt 2 + 2 = 3 + 2 \sqrt 2 \\[1em] (1 + \sqrt 2)^3 &=& (3 + 2 \sqrt 2)(1 + \sqrt 2) = 7 + 5 \sqrt 2 \\[1em] (1 + \sqrt 2)^4 &=& (7 + 5 \sqrt 2) (1 + \sqrt 2) = 17 + 12 \sqrt 2 \end{array}

and so on. It quickly becomes clear (if you have not already seen this kind of thing before) that (1 + \sqrt 2)^n will always be of the form a + b \sqrt 2. Let’s define a_n and b_n to be the coefficients of the nth power of (1 + \sqrt 2), that is, (1 + \sqrt 2)^n = a_n + b_n \sqrt 2. Now the natural question is to wonder what, if anything, can we say about the coefficients a_n and b_n? Quite a lot, as it turns out!

We can start by working out what happens when we multiply (1 + \sqrt 2)^n = (a_n + b_n \sqrt 2) by another copy of (1 + \sqrt 2):

\displaystyle (1 + \sqrt 2)^{n+1} = (a_n + b_n \sqrt 2)(1 + \sqrt 2) = (a_n + 2b_n) + (a_n + b_n) \sqrt 2

But (1 + \sqrt 2)^{n+1} = a_{n+1} + b_{n+1} \sqrt 2 by definition, so this means that a_{n+1} = a_n + 2b_n and b_{n+1} = a_n + b_n. As for base cases, we also know that (1 + \sqrt 2)^0 = 1 + 0\sqrt 2, so a_0 = 1 and b_0 = 0. From this point it is easy to quickly make a table of some of the values of a_n and b_n:

\displaystyle \begin{array}{ccc} n & a_n & b_n \\ \hline 0 & 1 & 0 \\ 1 & 1 & 1 \\ 2 & 3 & 2 \\ 3 & 7 & 5 \\ 4 & 17 & 12 \\ 5 & 41 & 29 \\ 6 & 99 & 70 \\ 7 & 239 & 169 \\ 8 & 577 & 408 \\ 9 & 1393 & 985 \end{array}

Each entry in the b_n column is the sum of the a_n and b_n from the previous row; each a_n is the sum of the previous a_n and twice the previous b_n. 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 a_n and b_n separately, such that each a_n only depends on previous values of a_n, and likewise each b_n only depends on previous b_n. I’ll explain how to do that next time, but leave it as a challenge for you in the meantime!

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in number theory, puzzles and tagged , , , , , . Bookmark the permalink.

8 Responses to The curious powers of 1 + sqrt 2: recurrences

  1. 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

  2. Thibault Vroonhove says:

    [Of course don’t read my comment if you don’t wanna spoil yourself]

    We can observe that \forall n\leq 1, a_{n+1}=2a_n+a_{n-1} and b_{n+1}=2b_n+b_{n-1} (each a_n is the sum of twice the previous one, and the one two rows above it – and the same pattern goes for the b_n).
    It is possible to prove it by induction, but let us do it another simple way:
    – notice that (1+\sqrt{2})^2 = 3+2\sqrt{2} = 2(1+\sqrt{2})+1.
    – it follows that (1+\sqrt{2})^{n+1} = 2(1+\sqrt{2})^n + (1+\sqrt{2})^{n-1}, if we multiply both sides of the equality by (1+\sqrt{2})^{n-1}.
    – by definition of a_n and b_n, we get a_{n+1}+b_{n+1}\sqrt{2} = (2a_n+a_{n-1})+(2b_n+b_{n-1})\sqrt{2}. Now, since the decomposition (1+\sqrt{2})^n = a_n+b_n\sqrt{2} where a_n and b_n are integers is unique (thanks to \sqrt{2}‘s irrationality), we must have that a_{n+1}=2a_n+a_{n-1} and b_{n+1}=2b_n+b_{n-1}.

  3. decourse says:

    I think I’ve seen those numbers before…

    Yes, \frac{a_n}{b_n} are the continued fraction convergents to \sqrt{2}.

  4. THANK YOU FOR THAT CLEVER SOLUTION TO (1 + SQRT(2))^500.
    Question:
    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 ?

    • Brent says:

      “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.

Comments are closed.