»  Solutions to puzzles in my National Review Online Diary

  January 2010

—————————

In my January diary I posed the following brain-teaser.

Suppose that s1, s2, s3, … is a strictly increasing sequence of positive integers such that the subsequences
ss1, ss2, ss3, … and ss1+1, ss2+1, ss3+1, …
are both arithmetic progressions. Prove that the sequence s1, s2, s3, … is itself an arithmetic progression.

—————————

Solution

First, some sequence basics. An integer sequence is a match-up between the ordinary counting numbers (excluding zero) and some subset of them. (I'm going to ignore negative numbers completely on this page, though the word "integer" technically embraces them.) The counting numbers are 1, 2, 3, 4, …, where the three dots indicate that you can go on for as long as you please. The matched-up subset is conventionally denoted with subscripts, as in our exercise here:  s1, s2, s3, …

An example of an integer sequence would be the prime numbers:  s1 = 2, s2 = 3, s3 = 5, s4 = 7, s5 = 11, and so on. A glance at The On-Line Encyclopedia of Integer Sequences would be instructive at this point.

An "arithmetic progression" is a particular kind of sequence, one in which consecutive terms differ by some constant number, the common difference. In the arithmetic progression 10, 13, 16, 19, 22, …, the common difference is 3. Obviously the sequence of primes is not an arithmetic progression.

From a first-order sequence like s1, s2, s3, … you can pluck out a second-order sequence, whose subscripts are derived somehow from the first-order sequence. The simplest case is  ss1, ss2, ss3, …, where the subscripts are the actual numbers in the first-order sequence. In the case of the primes, this particular second-order sequence would be  s2, s3, s5, s7, s11, …  In other words, it is  3, 5, 11, 17, 31, 41, …  You can also of course form third-, fourth-, …, N-th-order sequences. The simplest example of a third-order sequence would be sss1, sss2, sss3,  …  In the case of the primes, this would be the sequence  5, 11, 31, 59, 127, 179, …

Don't worry: third-order is the furthest I shall go here.

—————————

Now some notation. I'll refer to the first-order sequence in our problem as "Sequence I" (i.e. Roman "one"). The two second-order sequences we're given I'll call "Sequence IIa" and "Sequence IIb." We're told that these are in fact arithmetic progressions. I'll call their common differences da and db, respectively. The differences between terms in Sequence I, the first-order sequence, I'll denote by t 's:  s2 − s1 = t1,  s3 − s2 = t2,  s4 − s3 = t3,  and so on. My task is to prove that all these t 's are in fact equal.

It is very important to notice that the t 's are bounded above. Any particular tn participates in a bunch of t 's adding up to da, and another bunch adding up to db.  Since we're told that Sequence I is strictly increasing, each term bigger than the previous one, the t 's are all positive. So none of them can be bigger than da or db. Let's denote by tmax the biggest value any t ever has. Since they're all positive, they are of course also bounded below. I'll use tmin to denote the smallest value ever attained.

—————————

I'll first show that an important subset of the t 's are all equal. I'll simultaneously show that da = db.

A picture helps here. I'll arbitrarily take the nonsense sequence  3, 6, 11, 13, 21, …  as Sequence I, my first-order sequence. (This sequence does not satisfy any of the conditions of the problem; I am just using it as a visual aid.)

Here is that first-order sequence laid out, with second-order Sequence IIa highlighted in red, second-order Sequence IIb in blue:

s1, s2s3, s4, s5, s6s7, s8, s9, s10s11s12, s13s14, s15, s16, s17, s18, s19, s20, s21s22,s23, s24, …

Consider the span from, say, s13 to s22. I can break it into three parts:  (1) s13 to s14, which is t13; (2) s14 to s21, which is the sum of a bunch of other t 's I'm not interested in — call it u13;  (3) s21 to s22, which is t21.

But from the fact of the second-order sequences  s3s6s11, … and s4s7s12, … being arithmetic progressions, I get these:

da = t13 + u13
db = u13 + t21

I can get rid of the pesky u13 just by subtracting:

db − da = t21 − t13

That is of course true all the way down the line. I can stack up a column of these results, going as far as I please:

db − da = t6 − t3
db − da = t11 − t6
db − da = t13 − t11
db − da = t21 − t13
 …  …  …
db − da = tsN+1 − tsN

There are actually N rows in that column. (Note that  t3  is  ts1, the first term of my arbitrary Sequence I being 3.)  If I add up all the rows I get this:

N × (db − da) = tsN +1 − t3

But since  (db − da) and t3 are fixed numbers and I can make N as big as I please, one of the following things must be true:  either (db − da) is zero, or tsN +1 can be indefinitely large. Since I know that the t 's are bounded above, it must be the case that (db − da) is zero. The two d's are equal:  I'll denote them by d.

Substituting back into the column, it follows that all those t 's are equal. I'll denote by t the number that they're all equal to.

Unfortunately this is only a subset of the t 's:  the subset  ts1ts2ts3, …  I still haven't proved that all the t 's are equal. Onward and upward.

—————————

What I'll prove now is that all the t 's in that subset are in fact equal to tmax.

First let me restate the thing I just proved:  For any n,  it is the case that ssn+1 − ssn is some fixed number t.

Let T be one of the numbers where  sT+1 − sT  is as big as it ever gets, equal to tmax.

Now consider this segment of second-order Sequence IIa, going from  sssT to  sssT +1:

sssT, sssT +1, sssT +2, sssT +3, …, sssT +1

A moment's thought will convince you that the number of terms in this segment is  (1 + sT +1 − sT).  The number of steps between them is of course one less than that, which is to say (see above) it is tmax; and, this being second-order Sequence IIa, each step is d.  The total span of this segment, last actual number minus first actual number, is therefore  d × tmax

Now visualize the s's in that segment imbedded (colored red) in the first-order sequence.

 …, s, s, s, s, s, sssTs, s, s, sssT +1s, s, s, s, s, s, s, sssT +2s, s, s, s, … … …, s, s, sssT +1s, s, s, …

(I've left out the subscripts of the non-red elements there, just for clarity.)

We know that the number of steps separating the first of those red elements from the last in Sequence IIa is  tmax.  That's the thing I just showed. What's the number of steps separating them in Sequence I? It's not hard to see that it's  ssT +1 − ssT.  But that's just the difference of two consecutive terms in second-order Sequence IIa! In other words, it's d.

So I have a total span, last actual number minus first actual number, of  d × tmax,  covering d steps in the first-order sequence. Since none of those d steps can be bigger than tmax, they must all be equal to tmax.  (If any of them were less than tmax, I wouldn't be able to attain that total d × tmax.)  In particular, the step from sssT to the following member of the first-order sequence, sssT +1, is equal to tmax.  But that is just t; so that infinite subset of the t 's that I proved all equal up above, are in fact all equal to tmax.

—————————

We're not home yet. I've only improved on my result about that particular subset of t 's, the ones separating each red first-order sequence member from the blue one following it.

However, the argument that I just made for  tmax  works just as well for tmin! It follows that all that subset of t 's that are equal to tmax are also equal to tmin, and therefore that tmax is equal to tmin.

If a sequence of numbers has its maximum value equal to its minimum value, the numbers are all the same.  Q.E.D.