Franklin Pezzuti Dyer

Home     Posts     CV     Contact     People

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 \sum_{n=1}^\infty x^{\lfloor 4n/3\rfloor} = x + x^2 + x^4 + x^5 + x^6 + x^8 + x^9 + x^{10} + x^{12} + ...

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 here on Wikipedia.
  • 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$.
  • 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.
  • 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 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


    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'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