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 $n$ th 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!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

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

Michael Paul Goldenberg says:

July 6, 2017 at 2:35 pm

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
- Brent says:
  
  July 6, 2017 at 10:28 pm
  
  Right! Can you prove it? (Without peeking at Thibault’s comment below? =)
Thibault Vroonhove says:

July 6, 2017 at 3:24 pm

[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}$ .
- Thibault Vroonhove says:
  
  July 6, 2017 at 3:26 pm
  
  * $\forall n\geq 1$ , oops !
- Brent says:
  
  July 6, 2017 at 10:27 pm
  
  Oh, very nice! I had a different proof, but I knew there had to be something like this.
decourse says:

July 7, 2017 at 1:46 am

I think I’ve seen those numbers before…

Yes, $\frac{a_n}{b_n}$ are the continued fraction convergents to $\sqrt{2}$ .
Jerry Friedman says:

July 11, 2017 at 12:09 pm

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:
  
  July 17, 2017 at 5:08 pm
  
  “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.