Franklin Pezzuti Dyer

Home     Posts     Resources     CV     Contact

Table of Contents

  1. The easy rational case
  2. Beatty sequences
  3. Exploiting staircase behavior
  4. Four auxiliary functions
  5. Additional identities

Beatty Series and Sums over Rationals

The exact value of the geometric series with ratio $x$ is well-known and easy to derive:

which converges for $|x|<1$. Recently I’ve been playing around with a similar type of series whose summand decreases almost geometrically, but with a twist. For example, consider the following series:

where $\alpha$ is some positive real constant, and the $\lfloor \cdot \rfloor$ denotes the floor or “greatest integer” function. When $\alpha\in \mathbb N$, this simply reduces to a geometric series, because $\lfloor \alpha n\rfloor = \alpha n$ when $\alpha$ is a natural number. Similarly, when $\alpha\in\mathbb Q$, it’s not quite a geometric series, but it can be reduced to a constant times a geometric series with a bit of casework. However, when $\alpha$ is irrational, this series is frustratingly difficult to calculate, and I haven’t been able to compute in closed-form a single non-trivial series of this form with $\alpha\notin \mathbb Q$ and $x\ne 0$.

Despite this difficulty, I’ve managed to come up with some interesting non-trivial identities relating series of this form to other series involving the expression $\lfloor \alpha n\rfloor$, which I’ll derive in this post.

The easy rational case

Let’s start by considering an example. Suppose $\alpha = 4/3$. Then the series in question is

The sequence of terms $x,x^2,x^4,x^5,...$ is not quite geometric, because the sequence of exponents $1,2,4,5,...$ doesn’t increase by the same value each time. In particular, the finite differences of this sequence are $+1,+2,+1,+1,+2,...$. The finite differences aren’t constant, but they are periodic, which allows us to rewrite the series in the following form by grouping sets of 3 consecutive terms together and factoring:

or, equivalently,

The infinite series in parentheses on the RHS is a geometric series, and we may evaluate it readily using our formula for the sum of a geometric series. This yields the following closed form formula for our series:

We can easily generalize this technique for $\alpha=p/q$ an arbitrary positive rational number in simplest form (that is, such that $p,q$ are coprime). In this case, we will be able to factor the sum in the following way:

where the polynomial $P(x)$ is given by the partial sum

Using our formula for the geometric series again, we may deduce the following:

Piece of cake! Now, why can’t we apply a similar factoring trick when $\alpha$ is irrational? The problem is that the exponent $\lfloor pn/q\rfloor$ increases by the same amount whenever $n$ increases by $+q$, meaning that although the terms do not decreasing geometrically, the groups consisting of $q$ consecutive terms do decrease geometrically. But the finite differences of $\lfloor \alpha n\rfloor$ behave erratically (i.e. aperiodically) when $\alpha$ is irrational, making factoring impossible. For instance, here are the numbers $\lfloor n\sqrt{2}\rfloor$ and their finite differences:

More on these sequences in a moment.

Beatty sequences

The sequence of natural numbers $\lfloor \alpha n\rfloor$ has a special name when $\alpha\notin\mathbb Q$ and $n$ ranges over the natural numbers: it is called a Beatty Sequence. These sequences have several nice properties which I will list briefly below, but I won’t go through the trouble of proving them, mainly because the proofs are not very complex and kinda tedious, and I’m trying to keep this post short. You can try to prove them as exercises, if you’re interested.

  1. $\lfloor \alpha n \rfloor$ differs from $\alpha n$ by at most $1$, and it is always less than $\alpha n$.
  2. The two Beatty Sequences $\lfloor \alpha n\rfloor$ and $\lfloor \beta n\rfloor$ form a partition of the natural numbers (that is, each natural number appears in exactly one of the two sequences) if and only if $\alpha^{-1}+\beta^{-1}=1$. This is the Rayleigh Theorem and a proof can be found here on Wikipedia.
  3. The finite differences $\lfloor \alpha (n+1)\rfloor - \lfloor \alpha n\rfloor$ of a Beatty Sequence are always equal to either $\lfloor \alpha\rfloor +1$ or $\lfloor \alpha\rfloor$.
  4. The above finite difference equals $\lfloor \alpha\rfloor + 1$ if $n$ is in the Beatty Sequence $\lfloor (1/{\alpha})n\rfloor$ (where ${\alpha}$ is the “fractional part” of $\alpha$, defined as $\alpha-\lfloor\alpha\rfloor$), and $\lfloor \alpha\rfloor$ otherwise.
  5. The finite differences of Beatty Sequences are aperiodic (i.e. the sequence of finite differences never repeats itself), which follows from the fact that $\alpha$ is irrational.

The Rayleigh Theorem allows us to prove one interesting identity involving the series we considered earlier. Let’s consider this series as a function of $\alpha$ and $x$, defined as follows:

We know that the Beatty Sequences $\lfloor \alpha^{-1}n\rfloor$ and $\lfloor (1-\alpha)^{-1} n\rfloor$ form a partition of the natural numbers, by the Rayleigh Theorem. This means that

Because every natural number appears in exactly one of the two sequences, each of the terms $x^n$ with $n\in\mathbb N$ appears exactly once in the sum of the two series, turning it into a simple geometric series. We may write this identity as a functional equation of $A$:

Other cool identities of similar series can be proven using the properties of Beatty Sequences that we’ve listed so far, such as the following:

Try to prove this as an exercise if you want, but we’ll prove it later using a totally different (and, in my opinion, much more powerful) technique.

Exploiting staircase behavior

In this section, I’ll describe an awesome technique that I first saw in this paper by Dr. Kevin O’Bryant. In subsequent sections, I’ll define a few “special functions” and show how this technique can be used to evaluate a wide variety of series related to Beatty Sequences in terms of these functions, and find other series identities and functional equations related to them.

The floor function $\alpha\mapsto \lfloor \alpha\rfloor$ is often referred to as a “staircase function” because its graph consists of a sequence of horizontal line segments (each of which contains its leftmost endpoint, but not its rightmost). This function has zero slope everywhere, but it increases by means of discontinuous “jumps” that occur at integer arguments. Note that

which is just another way of saying that the floor function has unit-sized “jumps” at the integers and no jumps elsewhere. Not only does it have no other discontinuous “jumps”, but it is also flat everywhere else (i.e. it has zero derivative, or zero slope, or is constant in between its “jumps”).

The graph of the function $\alpha\mapsto \lfloor\alpha n\rfloor$ also looks like a staircase, but with shorter steps (the line segments in this graph have length $1/n$, instead of unit length). The discontinuous unit “jumps” of this function occur not when $\alpha$ is an integer, but when $\alpha$ is an integer multiple of $1/n$.

Finally, consider the function $\alpha\mapsto x^{\lfloor \alpha n\rfloor}$. Again, this function has discontinuous jumps when $n$ is an integer multiple of $1/n$, but these jumps are not necessarily of unit size. Instead, we have

Finally, we are in a good position to consider the function that we defined earlier:

Consider $A$ as a function of varying $\alpha$, with $x$ held constant. The term $x^{\lfloor n\alpha\rfloor}$ has a “jump” discontinuity at the integer multiples of $1/n$, meaning that this infinite sum has jump discontinuities at all integer multiples of $1/n$ where $n$ is any natural number. In other words, $A$ has a jump discontinuity at every rational value $\alpha=p/q$! Can we figure out how much it “jumps” by as $\alpha$ increases from $p/q-h$ to $p/q$, for small $h$?

Well, we know that at $\alpha=p/q$, the term $x^{\lfloor \alpha n\rfloor}$ has a jump discontinuity if and only if $\alpha$ is a multiple of $1/n$. This is true if and only if $n$ is a multiple of $q$, or $n=qk$ for some integer $k$. If we denote the “jump” of $A$ at $\alpha=p/q$ as $\Delta A(p/q,x)$, this allows us to conclude that

Using the fact that $\lfloor (p/q)qk\rfloor = pk$, this sum becomes an infinite series, allowing us to conclude that

So we know the values of all of the “jumps” of $A$! Great, what does this get us?

Well, recall that all of the terms of $A$ are “flat” everywhere, that is, they have zero slope/derivative. This means that all increases in the value of $A$ are caused by one or more of the “jumps” we’ve discussed. In particular, if we know the value of $A(\alpha_0,x)$ and we want to know the value of $A(\alpha_1,x)$ for some $\alpha_1 > \alpha_0$, we can just start with the value of $A(\alpha_0,x)$ and add up the sizes of all of the jumps between $\alpha=\alpha_0$ and $\alpha=\alpha_1$, which will give us the value of $A(\alpha_1,x)$! In other words,

Where the summation on the RHS is taken over rational numbers $p/q$ in simplest form (i.e. with $p,q$ coprime). Since $|x|<1$, the value of $A(\alpha,x)$ approaches $0$ as $\alpha\to\infty$, meaning that if we let $\alpha\to\infty$ in the above expression, we obtain

Rearranging a bit, and replacing $\alpha_0$ with $\alpha$, we have that

We’ve rewritten this quasi-geometric series as a summation taken over all rational numbers greater than a certain real number $\alpha$! Take a moment to convince yourself that the summation on the RHS actually converges. For convenience later in the post, we’ll define an normalized form of the function $A$, which we’ll call $\tilde{A}$, which isolates just this series:

Just in case the sum over rationals on the RHS looks nasty to you and its utility is unclear, I’ll now use this technique to briefly prove the series identity stated as an exercise at the end of the previous section. Consider the series-defined function

The term $\lfloor \alpha n\rfloor x^n$ is a staircase function of $\alpha$, with a “jump” at the integer multiples of $1/n$ of magnitude $x^n$. This means that $D$ has jumps at all rational values $\alpha=p/q$, with magnitudes given by

Using similar reasoning to before, we may conclude that

If we notice that $D(0,x)=0$, we may substitute $\alpha_0\to 0$ and $\alpha_1\to \alpha$ in the above expression to obtain

However, notice that the condition $0\lt p/q\le \alpha$ is equivalent to the condition $1/\alpha \lt q/p$, allowing us to write

or, equivalently,

Now notice: this exact same sum over rational numbers appears in the formula we derived for $A$, but with an argument of $\alpha$ instead of $1/\alpha$! Thus, combining (i) and (ii) allows us to deduce that

or

Crazy! We’ll soon use sums over rational numbers to derive several other more complex series identities like this (which, unlike this one, would be infeasible to prove using just simple known properties of Beatty Sequences). Stay tuned.

Four auxiliary functions

I’d like to define the following four “auxiliary” functions as follows, because I’ve noticed that many Beatty-related sums can be expressed in terms of values of these functions:

From the summation representation of $\tilde{A}$ that we determined earlier, we may immediately see how to express $\tilde{A}$ in terms of these functions:

because the sum $\theta_{00}$ covers the case of fractions $p/q$ with even denominators, and the sum $\theta_{10}$ covers the case with odd denominators, meaning that together they cover all rational numbers $p/q>\alpha$.

It happens that we can derive another relation relating $\tilde{A}$ to the $\theta$ functions, in a way that is inequivalent to the above identity. Consider what happens to $\tilde{A}$ when the argument $\alpha$ is doubled. Through the following sequence of manipulations of the rational numbers over which the summand ranges, we can deduce the following:

First, we split the sum over rationals into two cases - one in which the numerator is even, and one in which it is odd. When the numerator is even, then the simplest-form fraction that results from dividing $p/q$ by $2$ is given by $(p/2)/q$, i.e. the numerator is halved. When the numerator is odd, however, the resulting fraction is $p/2q$, and the denominator is doubled. Since the summand depends only on the numerator $p$ and not the denominator $q$, the former transformation alters the summand, whereas the latter does not. Thus, we have the following identity:

By combining this with our previous identity linking $\tilde{A}$ to $\theta_{00}$ and $\theta_{11}$, we may obtain the following corollary:

Let's do one more example. Consider the following series-defined function which is similar to $A$:

Let's begin by finding a representation for $B$ in terms of a sum over the rational numbers. We must first find out when the nth term of the sum, $x^{\lfloor \alpha (2n-1)\rfloor}$ has "jumps" as $\alpha$ increases. Using our explorations of the floor function earlier, we know that this function of $\alpha$ has "jumps" whenever $\alpha$ is an integer multiple of $1/(2n-1)$ - in other words, whenever $\alpha$ is a rational number whose denominator evenly divides $2n-1$, or when $\alpha=p/q$ with $q|2n-1$. Since $q$ must be odd, we may write $2n-1=q(2k-1)$ for some natural number $k$, in which case the "jump" at this value of $\alpha$ equals $x^{p(2k-1)}(1-1/x)$. This allows us to write

If we again define a normalized version of $B$ as $\tilde{B}=\frac{x}{1-x}B$, then we have

Here's another example - I won't go through the trouble of proving this one, but the proof is very similar. If we define

then the normalized version of $C$, defined as $\tilde{C}:=\frac{\sqrt{x}}{1-x}C$, satisfies

Additional identities

I've derived several more interesting identities involving $\tilde{A}, \tilde{B}, \tilde{C}$, and the $\theta$ functions, more than I care to prove algebraically in this post. However, I'll document the most interesting ones here. If you're curious how they're derived, try to figure them out yourselves - the techniques are very similar, but some of them involve more sophisticated manipulations of the rational numbers $p/q$ over which the summations are taken, and more involved parity-related casework. Here are my favorites:

That's all I've got for now! If I come up with more cool identities later, I'll post them here.

back to home page