## October 2022

—————————

In the Math Corner of my January 2021 Diary I included the following brainteaser, which
I'd found in the "Problems" section of the January 2021 *MAA Monthly*. The problem was submitted by Jovan Vukmirovic of Belgrade,
Serbia.

Problem: Letx_{1},x_{2}, andx_{3}be real numbers, and definex_{n}forn≥ 4 byx_{n}= max{x_{n−3},x_{n−1}} −x_{n−2}. Show that the sequencex_{1},x_{2}, … is either convergent or eventually periodic, and find all triples (x_{1},x_{2},x_{3}) for which it is converegent.

I added the following comments:

Well, that caught my eye so I fiddled with it for a couple of hours …and got absolutely nowhere. Usually I can at least glimpse a way to the solution, even when I can't be bothered to slog my way through to the end. Here I got no handle on the thing at all.

The time lag between a problem's being posed [i.e. in theMAA Monthly] and its solution being posted is considerable; average about fifteen months, I think. So if you are stumped by a problem in this January 2021 issue, you'll probably have to wait until Spring of 2022 to be destumped

So now I have to wait until next year for a worked solution, unless some reader more mathematically adept than I am — not a high bar — can help me out.

No reader could; and the time lag on this one was actually twenty-one months. A solution appeared in the October 2022 *MAA
Monthly*.

I can't truthfully say I'd been holding my breath those twenty-one months. After that early fruitless fiddling I'd forgotten all about it. Seeing the solution in this October 2022 issue, though, I thought I should present it and pass some general comments.

First, some orientation.

—————————

**• Orientation:** The region of math we are in here is the study of *sequences*.

A sequence is defined in all generality to be an ordered set of numbers. The numbers in a sequence are called its *terms*. Here's a
sequence with four terms:

7, −104, π³, 19 − 4.75i.

Yes; that sequence consists of a positive integer, a negative integer, an irrational number, and a complex number. That's a weird mix, but it's a sequence. Note that this:

π³, 19 − 4.75i, 7, −104.

is the same *set* of numbers, but a different *sequence*. That's because of the word "ordered" in the
definition. Sequences with the same terms but in a different order are *different sequences*.

Neither of those is a sequence a mathematician would want to bother with, though. For one thing, there's too much of a mix of different
kinds of numbers having no apparent relation to each other. For another, there are only four numbers in each sequence. These are *finite*
sequences. Bo-ring!

A sequence is mathematically interesting (usually) when (1) all its numbers are of the same kind, generated by some rule, and (2) they
continue for ever — it's an *infinite* sequence. The sequences we're dealing with here, for example, which I have christened
Vukmirovic's sequences, consist only of real numbers; and they are infinite.

[*Note 1*: If you want to see a lot of fun sequences, check out the
Online Ecyclopedia of Integer Sequences. All the numbers in these sequences are, duh, integers, either
positive or negative. I get some credits in the OEIS: see here, for example.]

[*Note 2*: The words "sequence" and "series" are sometimes confused. A sequence is, as stated, an ordered
list of numbers, generally written with the numbers separated by commas. A series is a single number that you get by adding up the terms of
a sequence, usually infinitely many of them.

1,a,a^{2},a^{3},a^{4}, …

is a sequence, presumably — to judge by the ellipsis — an infinite one; but

1 +a+a^{2}+a^{3}+a^{4}+ …

is a series.]

In what follows I'll be dealing with infinite sequences of real numbers.

**• The algebra of sequences:** The terms of a sequence are usually governed by some interesting rule. The sequence
2, 4, 8, 16, 32, … consists of the powers of 2 in order; its *n*-th term is 2^{n}.
Interesting!

When we're dealing with a sequence whose terms we don't know, we of course use algebra, with letters to stand for whatever the numbers might be. We normally just use a single letter subscripted, in fact. So a series under general discussion looks like this:

a_{1},a_{2},a_{3},a_{4}, …

Sometimes it's more convenient to start the subscripting at zero:

a_{0},a_{1},a_{2},a_{3}, …

Fielder's choice. It's important to know which style is in play, though. If it's the second style, starting with *a*_{0},
you have to keep remembering that the (for example) fourth term, as colloquially understood, is *a*_{3}.

In what follows I'll stick with the first way of subscripting: *a*_{1}, *a*_{2},
*a*_{3}, *a*_{4}, …

**• Recursive sequences:** In the universe of sequences there is a category of sequences that are
*recursive*. Each term in a recursive sequence is defined by
some fixed formula involving preceding terms.

The best-known recursive sequence by far is the Fibonacci sequence 1, 1, 2, 3, 5, 8, 13,
21, 34, … in which each term after the second is the sum of the previous two terms. So once you get past the first two terms, the
formula for the *n*-th term *a*_{n} is

a_{n}=a_{n-1}+a_{n-2}

Or, what amounts to the same thing:

a_{n+2}=a_{n+1}+a_{n}forn≥ 1.

Or equivalently, just moving terms across,

a_{n+2}−a_{n+1}−a_{n}= 0 forn≥ 1.

**• The characteristic polynomial:** Written in that last style, the Fibonacci formula is very suggestive to a
mathematician's eye. It reminds him of a polynomial equation:

x^{2}−x− 1 = 0.

That similarity is, as I said, just suggestive — a mere accidental artefact of the way we write mathematical expressions. It would be surprising to find that there is any actual connection between sequence recursion formulas and polynomial equations. They don't seem to be related to each other in any obvious way.

Math, however, like life, is full of surprises. That polynomial equation *is* very intimately connected with the Fibonacci sequence.
It has two solutions, which you can easily find using the good old quadratic-equation formula. Those two roots are (1 + √5)/2 and
(1 − √5)/2. They work out to approximately 1.618034 and −0.618034. I'll just call them α and β for
convenience.

Now compute (α^{9} − β^{9})/√5. Answer: 34. That's the 9th Fibonacci number!
(Remember β is a negative number, so its 9th power is also negative.)

That works for any positive integer, not only 9. For a proof, see endnote 35 in my book
*Unknown Quantity*.

So yes: there is an intimate connection between the sequence generated by a recursion formula and the polynomial that formula suggests to
us. A recursive sequence has a *characteristic polynomial*. The characteristic polynomial of the Fibonacci sequence is
*x*^{2} − *x* − 1 .

I went through all that because the notion of a characteristic polynomial turns up in the solution of this brainteaser. The theory of characteristic polynomials is quite deep and tangled, so I won't go any further into it here. You can find plenty of descriptions on the internet: here for example.

—————————

**• The Vukmirovic sequences:** After all that orientation, let's look at the Vukmirovic sequences. Here's the problem
statement once again, with my *a*'s in place of Vukmirovic's *x*'s.

Problem: Leta_{1},a_{2}, anda_{3}be real numbers, and definea_{n}forn≥ 4 bya_{n}= max{a_{n−3},a_{n−1}} −a_{n−2}. Show that the sequencea_{1},a_{2}, … is either convergent or eventually periodic, and find all triples (a_{1},a_{2},a_{3}) for which it is converegent.

Plainly these are recursive sequences. The recursion rule given here doesn't suggest a polynomial, though. It's too messed up by that
max{*a*_{n−3}, *a*_{n−1}} item.

That item does, however, suggest a strategy. It suggests that an important factor here is the relative sizes of a term and its next-but-one term.

OK, let's divide the terms of a Vukmirovic sequence into two types, downers and uppers. A term is a downer if the next-but-one term is
smaller: *a*_{n} > *a*_{n+2}. You *descend* when advancing from this term to its next-but-one term,
see? If a term's not a downer, it's an upper:
*a*_{n} ≤ *a*_{n+2}. Going from an upper to its next-but-one you ascend, or stay equal.

This does indeed turn out to be a key to the problem.

**• Key to the problem:** Either there is, or there is not, somewhere in the sequence (possibly the very first term), an
upper term followed immediately by a downer. Algebraically: There is some *n* (possibly *n* = 1) for which
*a*_{n} ≤ *a*_{n+2} and
*a*_{n+1} > *a*_{n+3}.

**• Case 1 — periodic:** If there *is* such a term, the sequence is periodic from some point onwards,
with period 4. Example:

7, 11, 2, −4, 9, 13, 4, −4, 9, 13, 4, −4, 9, 13, 4, …

You can easily verify that the recursion rule for a Vukmirovic sequence is being followed there. The terms are downers and uppers like
this: D, D, U, U, D, D, U, U, D, D, U, U, D, D, U, …. The first case
of an upper followed immediately by a downer is at *a*_{4} and the sequence is periodic from then on with period 4.

(A sequence may take longer to get periodic, but it will begin to do so no later than *a*_{n+3}.)

To prove this sub-result in all generality, it's easier on the eye to call the upper term *a*, the immediately-following downer term
*b*, and so on. The next term, *c*, is by definition, greater than or equal to *a*, so that — also by
definition — the *next* term is *c* − *b*.

After that you hit a logical fork depending on whether *c* ≤ *b* − *c* or
*c* > *b* − *c*; but whichever prong of the fork you follow, the sequence goes periodic with period
4. Trust me … or just work your way through the logic.

So: If there *is*, somewhere in the sequence, an upper term followed immediately by a downer, then the sequence is periodic for ever
onwards, with period 4. I'm calling that Case 1.

What if there *isn't* any such term in the sequence? What if no upper term is *ever* followed immediately by a downer?

In that event it must be the case that *either* all the terms from some point on (perhaps the very first term) are uppers
*or* every single term in the sequence, starting with the first, is a downer. I'll call these Cases 2 and 3. Just pause to work through the
logic of that, to see *why* this "must be the case."

[*Pause*.]

**• Case 2 — periodic and convergent:** All the terms from some point on (perhaps the very first
term) are uppers. Call the first of these uppers

*a*

_{n}. Then

*a*

_{n+3}, which by definition is bigger than

*a*

_{n+1}, is equal to

*a*

_{n+2}−

*a*

_{n+1}from that point onwards.

If you keep tracking forward through the sequence from there using the recursion formula you have soon —
by the time you get to *a*_{n+7} — collected the facts that

−a_{n+1}≥a_{n+2}

and also

a_{n+1}≥ −a_{n+2}

The only way to satisfy both those inequalities is for both *a*_{n+1} and *a*_{n+2} to be
zero. It then easily follows that the only possible form for this sequence is

a_{1}, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, …

with *a*_{1} some negative number, or zero. That sequence is convergent *and* periodic, although trivially so in both
cases.

**• Case 3 — nontrivially convergent:** If every single term in the sequence is a downer, then
*a*_{4} = *a*_{1} − *a*_{2},
*a*_{5} = *a*_{2} − *a*_{3}, and so on. Generally:

a_{n+3}+a_{n+1}−a_{n}= 0.

The corresponding characteristic polynomial is
*x*^{3} + *x* − 1. Solving the equation

x^{3}+x− 1 = 0

(see page 60 of
*Unknown Quantity*) you
find that there is only one real root, value 0.682327803828…. The cube of that number is 0.317672196171…. So yes: if you
add the number to its cube and subtract 1, you do indeed get zero.

Here we get deeper into the math of characteristic polynomials than I want to go. Suffice it to say that if we refer to that root as λ, the theory proves that the sequence must have the form

a_{1},a_{1}λ,a_{1}λ^{2},a_{1}λ^{3},a_{1}λ^{4}, …

for some positive number *a*_{1}. Because λ is less than one, its powers get smaller and smaller; the sequence
converges to zero.

Note that the sequence as laid out there does indeed follow the Vukmirovic recursion. The eighth term
*a*_{1}λ^{7}, for example, is, by the recursion rule and the fact that each term is smaller than the previous term,
*a*_{1}λ^{4} − *a*_{1}λ^{5}. That factorizes to
*a*_{1}λ^{4}(1 − λ). The expression in parentheses there, though, is, by the characteristic
polynomial equation *x*^{3} + *x* − 1 = 0, equal to λ^{3}.

Here you get at least a glimpse of how, when generating the sequence, the recursion rule and the characteristic polynomial are related.