The Astonishing Behavior of Recursive Sequences

In mathematics, simple rules can unlock universes of complexity and beauty. Take the famous Fibonacci sequence, which is defined as follows: It begins with 1 and 1, and each subsequent number is the sum of the previous two. The first few numbers are:

1, 1, 2, 3, 5, 8, 13, 21, 34 …

Simple, yes, but this unassuming recipe gives rise to a pattern of far-reaching significance, one that appears to be woven into the very fabric of the natural world. It’s seen in the whorls of nautilus shells, the bones in our fingers, and the arrangement of leaves on tree branches. Its mathematical reach extends to geometry, algebra and probability, among other areas. Eight centuries since the sequence was introduced to the West — Indian mathematicians studied it long before Fibonacci — the numbers continue to attract the interest of researchers, a testament to how much mathematical depth can underlie even the most elementary number sequence.

In the Fibonacci sequence, every term builds on the ones that came before it. Such recursive sequences can exhibit a wide range of behaviors, some wonderfully counterintuitive. Take, for instance, a curious family of sequences first described in the 1980s by the American mathematician Michael Somos.

Like the Fibonacci sequence, a Somos sequence starts with a series of ones. A Somos-k sequence starts with k of them. Each new term of a Somos-k sequence is defined by pairing off previous terms, multiplying each pair together, adding up the pairs, and then dividing by the term k positions back in the sequence.

The sequences aren’t very interesting if k equals 1, 2 or 3 — they are just a series of repeating ones. But for k = 4, 5, 6 or 7 the sequences have a weird property. Even though there is a lot of division involved, fractions don’t appear.

“Normally we don’t have this kind of phenomenon,” Somos said. “It’s a deceptively simple recurrence, similar to Fibonacci. But there’s a lot behind that simplicity.”

Other mathematicians continue to uncover startling connections between Somos sequences and seemingly unrelated areas of mathematics. One paper posted in July uses them to construct solutions to a system of differential equations used to model everything from predator-prey interactions to waves traveling in high-energy plasmas. They are also used to study the structure of mathematical objects called cluster algebras and are connected to elliptic curves — which were the key to cracking Fermat’s Last Theorem.

Janice Malouf, a graduate student at the University of Illinois, published the first proof that Somos-4 and Somos-5 sequences are integral (meaning all of their terms are integers) in 1992. Other proofs of the same result by different mathematicians appeared around the same time, along with proofs that the Somos-6 and Somos-7 sequences are integral.

This strange property of Somos sequences astounded mathematicians. “Somos sequences intrigued me as soon as I learned about them,” said James Propp, a professor of mathematics at the University of Massachusetts, Lowell. “The fact that Somos-4 through Somos-7 always give integers, no matter how far out you go, seemed like a miracle when you viewed things from a naïve perspective. So a different perspective was required.”

Propp found a fresh perspective in the early 2000s, when he and his colleagues discovered that the numbers in the Somos-4 sequence are actually counting something. The terms in the sequence correspond to structures found in certain graphs. For some graphs, it’s possible to pair up vertices (dots) with edges (lines) so that every vertex is connected to exactly one other vertex — there are no unpaired vertices, and no vertex connected to more than one edge. The terms in the Somos-4 sequence count the number of different perfect matchings for a particular sequence of graphs​.

The discovery not only offered a new perspective on Somos sequences, but also introduced new ways to think about and analyze graph transformations. Propp and his students celebrated by having the result put on a T-shirt.

“To me a big part of the allure of math is when you arrive at the same destination by different paths and it seems like something miraculous or deep is going on,” Propp said. “The cool thing about these sequences is there are various points of view that explain why you get integers. There are hidden depths there.”

The story changes for higher-numbered Somos sequences. The first 18 terms of Somos-8 are integers, but the 19th term is a fraction. Every Somos sequence after that also contains fractional values.

Another type of sequence, developed by the German mathematician Fritz Göbel in the 1970s, is an interesting counterpoint to the Somos sequences. The nth term of the Göbel sequence is defined as the sum of the squares of all the previous terms, plus 1, divided by n. Like the Somos sequences, the Göbel sequence involves division, so we might expect that terms won’t remain integers. But for a while — as the sequence grows enormous — they seem to be.

The 10th term in the Göbel sequence is about 1.5 million, the 11th 267-some billion. The 43rd term is far too large to calculate — it has some 178 billion digits. But in 1975, the Dutch mathematician Hendrik Lenstra showed that unlike the first 42 terms, this 43rd term is not an integer.

Göbel sequences can be generalized by replacing the squares in the sum with cubes, fourth powers, or even higher exponents. (Under this convention, his original sequence is called a 2-Göbel sequence.) These sequences also display a surprising trend of starting with an extended stretch of integer terms. In 1988, Henry Ibstedt showed that the first 89 terms of the 3-Göbel sequence (which uses cubes instead of squares) are integers, but the 90th isn’t. Subsequent research on other Göbel sequences found even longer stretches. The 31-Göbel sequence, for instance, kicks off with a whopping 1,077 integer terms.

In July, the Kyushu University mathematicians Rinnosuke Matsuhira, Toshiki Matsusaka and Koki Tsuchida shared a paper showing that for a k-Göbel sequence, no matter the choice of k, the first 19 terms of the sequence are always integers. They were inspired to look into the question by a Japanese manga called Seisū-tan, which translates to “The Tale of Integers.” A frame in the comic book asked readers to figure out the minimum possible value of N_k, the point at which a k-Göbel sequence ceases to produce integer terms. The three mathematicians set out to answer the question. “The unexpected persistence of integers for such an extended duration contradicts our intuition,” Matsusaka said.“When phenomena occur contrary to intuition, I believe there is always beauty present.”

They found a pattern of repeating behavior as k increases. By focusing on a finite number of repeating cases, they made the calculation tractable, and they were able to complete the proof.

A closer look at the sequence N_k reveals another surprise: N_k is prime far more often than you would expect if it were purely random. “With the k-Göbel sequence it’s not just remarkable that they’re integers,” said Richard Green, a mathematician at the University of Colorado. “What’s remarkable is that the prime numbers show up so often. That makes it look like something deeper might be going on.”

Though the new paper presents a proof that N_k is always at least 19, it’s not known if it is always finite, or if there exists a k for which the sequence contains integers indefinitely. “N_k behaves mysteriously. … There is a fundamental desire to comprehend its underlying pattern,” Matsusaka said. “It might be akin to the joy I felt as a child when solving puzzles given by teachers. Even now, those sentiments from that time linger within me.”