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: Let x1, x2, and x3 be real numbers, and define xn for n ≥ 4 by xn = max{xn−3, xn−1} − xn−2. Show that the sequence x1, x2, … is either convergent or eventually periodic, and find all triples (x1, x2, x3) 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 the MAA 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, a2, a3, a4, …
is a sequence, presumably — to judge by the ellipsis — an infinite one; but
1 + a + a2 + a3 + a4 + …
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 2n. 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:
a1, a2, a3, a4, …
Sometimes it's more convenient to start the subscripting at zero:
a0, a1, a2, a3, …
Fielder's choice. It's important to know which style is in play, though. If it's the second style, starting with a0, you have to keep remembering that the (for example) fourth term, as colloquially understood, is a3.
In what follows I'll stick with the first way of subscripting: a1, a2, a3, a4, …
• 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 an is
an = an-1 + an-2
Or, what amounts to the same thing:
an+2 = an+1 + an for n ≥ 1.
Or equivalently, just moving terms across,
an+2 − an+1 − an = 0 for n ≥ 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:
x2 − 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 x2 − 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: Let a1, a2, and a3 be real numbers, and define an for n ≥ 4 by an = max{an−3, an−1} − an−2. Show that the sequence a1, a2, … is either convergent or eventually periodic, and find all triples (a1, a2, a3) 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{an−3, an−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: an > an+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: an ≤ an+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 an ≤ an+2 and an+1 > an+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 a4 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 an+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 an. Then an+3, which by definition is bigger than an+1, is equal to an+2 − an+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 an+7 — collected the facts that
−an+1 ≥ an+2
and also
an+1 ≥ −an+2
The only way to satisfy both those inequalities is for both an+1 and an+2 to be zero. It then easily follows that the only possible form for this sequence is
a1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, …
with a1 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 a4 = a1 − a2, a5 = a2 − a3, and so on. Generally:
an+3 + an+1 − an = 0.
The corresponding characteristic polynomial is x3 + x − 1. Solving the equation
x3 + 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
a1, a1λ, a1λ2, a1λ3, a1λ4, …
for some positive number a1. 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 a1λ7, for example, is, by the recursion rule and the fact that each term is smaller than the previous term, a1λ4 − a1λ5. That factorizes to a1λ4(1 − λ). The expression in parentheses there, though, is, by the characteristic polynomial equation x3 + 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.