Yet another thing about the golden ratio Part II

While I’m assuming you read the first post, I’ll recall where we left off. I noted that the numbers \(l_n = \varphi^n + \bar{\varphi}^n\)¹ satisfy the relationship

\[l_n = l_{n-1} + l_{n-2}\]

Thus, if we prove that $l_n$ follow this recurrence relation, we can compute $l_0 = 2, l_1 = 1$ by hand, and then we have proved that every $\varphi^n +\bar{\varphi}^n$ is an integer. As $\bar{\varphi}^n\rightarrow 0$ exponentially fast, this would conclude a proof that powers of the golden ratio get closer and closer to being integral: their distance to the nearest integer approaches $0$. So, lets get to it! All we’ll need are Taylor’s Theorem and a little bit on generating functions.

Taylors Theorem and a little bit on Generating Functions

Recall from calculus that if one has an infinitely differentiable function $f$ around a neighborhood of $0$, we can form the taylor series

\[f(x) = \sum_{n=0}^\infty \frac{f^{(n)}(0)}{n!}x^n\]

and this equality holds within a neighborhood of some radius $r$ around $0$.² Now, what may have been left out of the calculus class, but is extraordinarily important, is that this theorem provides a dictionary between functions and sequences. From this perspective, we call these functions generating functions. Lets look at a few examples of generating functions with their corresponding sequences:

\[\begin{align} \frac{1}{1-z} &\leftrightarrow 1,1,1,1,\ldots, g_n = 1\\[0.8em] \frac{1}{1-az} &\leftrightarrow 1,a,a^2,a^3,\ldots, g_n = a^n\\[0.8em] \frac{1}{(1-z)^2} &\leftrightarrow 1,2,3,4,\ldots, g_n = n\\[0.8em] \frac{1}{1-z-z^2} &\leftrightarrow 1,1,2,3,\ldots, g_n = g_{n-1}+g_{n-2}, g_0=g_1=1, \href{https://en.wikipedia.org/wiki/Fibonacci_sequence}{\text{Fibonacci Numbers}}\\[0.8em] \frac{1 - \sqrt{1-4z}}{2z} &\leftrightarrow 1,1,2,5,\ldots, g_n = \frac{1}{n+1}\binom{2n}{n}, \href{https://en.wikipedia.org/wiki/Catalan_number}{\text{Catalan Numbers}}\\[0.8em] \prod_{m=0}^\infty \frac{1}{1-z^m} &\leftrightarrow 1,1,2,3,\ldots, g_n \sim \frac{1}{4n\sqrt{3}}e^{\pi \sqrt{\frac{2n}{3}}}, \href{https://en.wikipedia.org/wiki/Partition_function_(number_theory)}{\text{Partition Numbers}}\\[0.8em] \text{tan}(z) &\leftrightarrow 0, 1, 0 ,\frac{1}{3},\ldots, g_n = \begin{cases} 0 & \text{if } n \text{ even}.\\ \frac{1}{n!}\cdot \#\text{binary heaps of size }n & \text{if } n \text{ odd.} \end{cases} \end{align}\]

While generating functions come in all shapes and sizes, luckily for this post all of the generating functions we’ll see will look like the first four. Now this correspondence is interesting, but you might be asking yourself “who cares?” That is, what does it do for us and how does it help solve the problem in this post? Well, the correspondence is deeper than just what is listed above. This correspondence allows you to turn operations on sequences into operations on functions. Then, using the algebra of functions and calculus³, we can learn things about the sequences.

There are many corresponding operations, but today we’ll only need two: addition and shift. Suppose you have two generating functions $F(z)$ and $G(z)$ corresponding to sequences $f_n$, $g_n$ respectively. The sum $H(z) = F(z)+G(z)$ is the generating function for $f_n + g_n$. For shift, $zF(z)$ is the generating function for the sequence $s_n = f_{n-1}$. It shifts the sequence right by one and puts in a leading $0$. You might already be catching on to how summation and shift are all you need to encode simple recurrence relations.

Solving our original problem with generating functions

Back to our problem, we have the sequence $l_n = \varphi^n + \bar{\varphi}^n$. What is it’s generating function? From the table above we already have generating functions for $s_n = a^n$ given by $\frac{1}{1-az}$ and so summing these together for $\varphi$, $\bar{\varphi}$ we get generating function

\[L(z) = \frac{1}{1-\varphi z} + \frac{1}{1 - \bar{\varphi}z} = \frac{2-z}{1-z-z^2}\]

Then, doing a little algebra, we find the following:

\[\begin{align} L(z) &= \frac{2-z}{1-z-z^2}\\[0.4em] (1-z-z^2)L(z) &= 2-z\\[0.4em] L(z) &= zL(z) + z^2L(z) + 2-z \end{align}\]

Well, what does this last equation say? First off, ignoring the the $2-z$ part which only affects the value of $l_0$ and $l_1$, $L(z) = zL(z) + z^2 L(z)$ says that $l_n$ is the sum of its right shift by one and right shift by two. That is, $l_n = l_{n-1} + l_{n-2}$, at least for $n\ge 2$. The $2-z$ part essentially ensures that $l_0 = 2$ and $l_1 = 1$: The $2$ sets $l_0 = 2$, and the $-z$ and $zL(z)$ sets $l_1= 1$.

Putting it all together, this is the end of the proof. With algebra on generating functions, we showed that $l_n = \varphi^n + \bar{\varphi}^n$ satisfies the recurrence relation $l_n = l_{n-1} + l_{n-2}$ and after manually checking that $l_0$ and $l_1$ are integers we are done! The lingering question is, is this a unique aspect of the golden ratio?

(Long) Afterword on Pisot–Vijayaraghavan numbers

No, not even close. Algebraic numbers with this property are pretty common and they are called Pisot–Vijayaraghavan numbers. PV numbers are algebraic integers, $\alpha$ whose powers, $\alpha^n$, get more and more integral with $n$. Equivalently, they are algebraic integers whose conjugates⁴ all have absolute value less than one. Its not so hard to produce an infinite sequence of examples: The positive roots of the polynomials $p_n$ for $n>2$ where

\[p_n = z^2 - nz + 1\]

are all PV numbers. The roots of this polynomial are $\frac{n \pm \sqrt{n^2-4}}{2}$ and one will clearly have norm greater than $1$ and since the product of the roots is $1$, the other will have norm less than $1$. Thus, they’ll be PV numbers.

A follow up question is, will these numbers also have an “elementary” proof that their powers become more and more integral using generating functions as above? The answer is also yes.

Suppose you have a PV number $\alpha_1$, with a minimal polynomial $p$ of degree $m$, and it has conjugates $\alpha_2,\ldots, \alpha_m$ all of absolute value less than $1$. First, calculate the initial $m$ values and show that they are integers: $\sum_i \alpha_i^k, 0,\le k<m$. For $k = 0$, this is $m$, for $k = 1$, this is $-p_{m-1}$ the negative of the $(m-1)$st coefficient of $p$. For higher $k$ this gets a little more involved.

Next, take the generating function for $g_n = \sum_i \alpha_i^n$,

\[G(z) = \sum_i \frac{1}{1- \alpha_i z} = \frac{h(z)}{p_{\text{rev}}(z)}\]

where $h(z)$ is an integer polynomial of degree $m-1$ and $p_{\text{rev}}(z) = \prod_i (1- \alpha_i z)$ is the reverse polynomial of the minimal polynomial $p$ (degree $m$ poly with the coefficients reflected).⁵ Then, doing a little algebra, we can get the relationship:

\[G(z) = (1 - p_{\text{rev}}(z)) G(z) + h(z)\]

and this will precisely express our recurrence relation. The $h(z)$ terms will make sure the initial $g_0,\ldots, g_m$ are correct. We also notice that the minimal polynomial $p$ encodes what the recurrence relation will be. Doing this out for the case $p = z^2 - 5z + 1$ as above, we have the following:

\[\begin{align*} \alpha &= \frac{5 + \sqrt{21}}{2} \approx 4.79128\\ \bar{\alpha} &= \frac{5-\sqrt{21}}{2}\approx 0.20871\\ g_0 &= 2\\ g_1 &= 5\\ p &= z^2 - 5z +1\\ p_{\text{rev}} &= z^2 - 5z + 1\\ g_n &= 5g_{n-1}-g_{n-2}\\[0.3em] G(z)&= \frac{2 -5z}{z^2-5z+1} \end{align*}\]

Throughout this process, I did not think of a way to prove generically that the initial $g_0,\ldots, g_{m-1}$ will be integers for $m>2$. Then… while writing this… I remembered Newton’s identities which would do the trick. In fact, they might work too well. They should let you skip all this generating function business as well. But I think I am going to call it here - don’t expect a part III explaining Newton’s identities. If you need more, check out Curtis McMullen’s lovely minor’s thesis on PV numbers which was handwritten in 1983.

Footnotes