## January 2010

—————————

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

Suppose that s_{1}, s_{2}, s_{3}, … is a strictly increasing sequence of positive integers such that the subsequencessare both arithmetic progressions. Prove that the sequence s_{s1}, s_{s2}, s_{s3}, … and s_{s1+1}, s_{s2+1}, s_{s3+1}, …_{1}, s_{2}, s_{3}, … 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:
s_{1}, s_{2}, s_{3}, …

An example of an integer sequence would be the prime numbers: s_{1} = 2, s_{2} = 3,
s_{3} = 5, s_{4} = 7, s_{5} = 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 s_{1}, s_{2}, s_{3}, … you can pluck
out a
*second-order sequence*, whose subscripts are derived somehow from the first-order sequence. The simplest case
is
s_{s1}, s_{s2}, s_{s3}, …, 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
s_{2}, s_{3}, s_{5}, s_{7}, s_{11}, … 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
s_{ss1}, s_{ss2}, s_{ss3}, …
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 *d _{a}* and

*d*, respectively. The differences between terms in Sequence I, the first-order sequence, I'll denote by

_{b}*t*'s: s

_{2}− s

_{1}=

*t*

_{1}, s

_{3}− s

_{2}=

*t*

_{2}, s

_{4}− s

_{3}=

*t*

_{3}, 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
*t _{n}*
participates in a bunch of

*t*'s adding up to

*d*, and another bunch adding up to

_{a}*d*. Since we're told that Sequence I is strictly increasing, each term bigger than the previous one, the

_{b}*t*'s are all positive. So none of them can be bigger than

*d*or

_{a}*d*. Let's denote by

_{b}*t*

_{max}the biggest value any

*t*ever has. Since they're all positive, they are of course also bounded below. I'll use

*t*

_{min}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
*d _{a}* =

*d*.

_{b}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:

s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}, s_{7}, s_{8}, s_{9}, s_{10}, s_{11}, s_{12}, s_{13}, s_{14}, s_{15}, s_{16}, s_{17}, s_{18}, s_{19}, s_{20}, s_{21}, s_{22},s_{23}, s_{24}, …

Consider the span from, say, s_{13} to s_{22}. I can break it
into three parts: (1) s_{13} to s_{14}, which is
*t*_{13}; (2) s_{14} to s_{21}, which is
the sum of a bunch of other *t* 's I'm not interested in — call it *u*_{13};
(3) s_{21} to s_{22}, which is
*t*_{21}.

But from the fact of the second-order sequences
s_{3}, s_{6}, s_{11}, … and s_{4}, s_{7}, s_{12}, …
being arithmetic progressions, I get these:

d=_{a}t_{13}+u_{13}

d=_{b}u_{13}+t_{21}

I can get rid of the pesky *u*_{13} just by subtracting:

d−_{b}d=_{a}t_{21}−t_{13}

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:

d−_{b}d=_{a}t_{6}−t_{3}

d−_{b}d=_{a}t_{11}−t_{6}

d−_{b}d=_{a}t_{13}−t_{11}

d−_{b}d=_{a}t_{21}−t_{13}

… … …

d−_{b}d=_{a}t_{sN+1}−t_{sN}

There are actually *N* rows in that column. (Note that *t*_{3} is
*t*_{s1}, the
first term of my arbitrary Sequence I being 3.) If I add up all the rows I get this:

N× (d−_{b}d) =_{a}t_{sN +1}−t_{3}

But since (*d _{b}* −

*d*) and

_{a}*t*

_{3}are fixed numbers and I can make

*N*as big as I please, one of the following things must be true:

*either*(

*d*−

_{b}*d*) is zero,

_{a}*or*

*t*

_{sN +1}can be indefinitely large. Since I know that the

*t*'s are bounded above, it must be the case that (

*d*−

_{b}*d*) is zero. The two d's are equal: I'll denote them by

_{a}*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
*t*_{s1}, *t*_{s2},
*t*_{s3}, … 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
*t*_{max}.

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

Let *T* be one of the numbers where
s_{T+1} − s_{T} is as
big as it ever gets, equal to *t*_{max}.

Now consider this segment of second-order Sequence IIa, going from s_{ssT}
to
s_{ssT +1}:

s_{ssT}, s_{ssT +1}, s_{ssT +2}, s_{ssT +3}, …, s_{ssT +1}

A moment's thought will convince you that the number of terms in this segment is
(1 + s_{T +1} − s_{T}). The number of steps
between them is of
course one less
than that, which is to say (see above) it is *t*_{max}; 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* × *t*_{max}

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

…, s, s, s, s, s, s_{ssT}, s, s, s, s_{ssT +1}, s, s, s, s, s, s, s, s_{ssT +2}, s, s, s, s, … … …, s, s, s_{ssT +1}, s, 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 *t*_{max}. 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
s_{sT +1} − s_{sT}. 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* × *t*_{max}, covering
*d* steps in the first-order sequence. Since none of those *d* steps can be bigger than
*t*_{max}, they must all be equal to
*t*_{max}. (If any of them were *less* than *t*_{max}, I wouldn't be able to
attain that total
*d* × *t*_{max}.) In particular, the step from
s_{ssT} to the following member of the first-order
sequence, s_{ssT +1}, is equal to *t*_{max}. 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
*t*_{max}.

—————————

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
*t*_{max} works just as well for
*t*_{min}! It follows that all that subset of *t* 's that are equal to
*t*_{max} are also equal to
*t*_{min}, and therefore that *t*_{max} is equal to *t*_{min}.

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