Four Operations Revisited – The Prisoner's Dilemma

D4. Four Operations Revisited

One of the great things about mathematics is that it’s always possible to look again at familiar things and discover something new. Sometimes this can happen when you combine well-known things in a new way.

For example, you’re probably familiar with the four basic operations of addition, subtraction, multiplication, and division. And you may have heard about various number sequences, such as the powers of two: 1, 2, 4, 8, 16, and so on. In that sequence, you obtain each term by adding the previous term to itself, or in symbols $a_{n} = a_{n - 1} + a_{n - 1}$ . Another similar sequence is the sum recurrence, also known as the Virahāṅka or Fibonacci sequence, in which you obtain each term by adding the previous term to the one before it, which can be represented as $b_{n} = b_{n - 1} + b_{n - 2}$ . The sum recurrence starts 1, 2, 3, 5, 8, 13, …

This dilemma challenges you to describe the long-term behavior of four different sequences. Unlike sequences $a$ and $b$ which just add one of the last two terms unchanged to the previous one, each of these sequences uses one of the four basic operations on the last two terms to determine what to add to the previous term. But first, what is meant by “long-term behavior?” The gold standard is a closed-form formula for the sequence — an expression for the $n$ th term that just involves $n,$ not previous terms. For example, the closed form for the powers of two is $a_{n} = 2^{n}$ . If there doesn’t seem to be a closed form, maybe you can find a formula that works when $n$ is bigger than some number, but might be off for the first few values. Or sometimes you can find a formula that is never exactly right, but gets closer and closer as $n$ gets large. An example of this possibility is the formula $b_{n} \approx ϕ^{n + 1} / \sqrt{5}$ for the sum recurrence, where $ϕ = (1 + \sqrt{5}) / 2$ is the golden ratio. All else failing, it could be one formula that’s always less than the sequence and another that is always greater — and hopefully you can get those two “bounding” formulas as close to each other as possible.

So all that said, can you describe the long term-behavior of each of the four following sequences? Each sequence starts with 1, then 2 (like $a$ and $b$ do), and thereafter adds the described quantity to the previous term to obtain the next term. If the described quantity is ever not a whole number, it should be rounded up to the next whole number.

One less than the sum of the previous two terms. So to obtain the third term of this sequence, you take $1 + 2 - 1 = 2$ , and add that to 2, to get 4.
One more than the difference of the previous two terms. This time, the amount you add to get the third term is $2 - 1 + 1 = 2$ , so the third term is again 4. (But don’t worry, this sequence will veer off from the first sequence soon!)
Half the product of the previous two terms. So in this case our next increment is $2 \cdot 1 / 2 = 1$ , and the third term will be 3.
Twice the quotient of the previous two terms. Now the next increment is $(2 / 1) \cdot 2 = 4$ , and the third term will be 6.

Which of these four sequences ultimately grows the slowest? You will see that by using each operation as part of an infinite cycle, we can get new, different behaviors. Happy sequence hunting!

This problem originally appeared in the Prisoner’s Dilemma in the 2022 Winter issue of the PMP Newsletter. Solutions are no longer being accepted for this Dilemma.

Show solution?

Solution.

As submitter Jesse Waite noted, a good first step in attacking one of these sequences is to write out (in symbols) the rule defining it, known as its recurrence relation. For example, if we denote the first series connected with addition by $c_{0}, c_{1}, c_{2}, \dots,$ its recurrence relation is $c_{n + 2} = c_{n + 1} + c_{n} - 1 + c_{n + 1} = 2 c_{n + 1} + c_{n} - 1.$

If the formula doesn’t ring a bell, a next good thing to do is write out the first several terms: $c_{1} = 1,$ $c_{2} = 2$ , $c_{3} = 4$ , $c_{4} = 9$ , $c_{5} = 21$ , $c_{6} = 50$ , $c_{7} = 120$ , $c_{8} = 289$ , and so on.

If the sequence still isn’t looking familiar, a good third step to try is to look at its “first difference sequence,” which just consists of the numbers you get by subtracting from each entry the one before it (you have to start from the second entry to do this). In this case, the sequence of first differences is $1, 2, 5, 12, 29, 70, 169, 408, \dots$

And now, if you have some experience with sequences, you could recognize these numbers as the Pell sequence $p_{n}$ , a close cousin of the familiar sum recurrence (also known as the Virahāṅka-Fibonacci sequence), in which $p_{n + 2} = 2 p_{n + 1} + p_{n}$ (instead of having $b_{n + 2} = b_{n + 1} + b_{n}$ as in the sum recurrence). Another way you could figure this out is by taking these first differences symbolically. If we let $c_{n}^{'} = c_{n + 1} - c_{n},$ then
$\begin{aligned} c_{n + 2}^{'} & = c_{n + 3} - c_{n + 2} = 2 c_{n + 2} + c_{n + 1} - (2 c_{n + 1} + c_{n} - 1) \\ = 2 (c_{n + 2} - c_{n + 1}) + (c_{n + 1} - c_{n}) = 2 c_{n + 1}^{'} + c_{n}^{'}, \end{aligned}$ exactly the recurrence for the Pell sequence.

So if the first differences of our sequence $c_{n}$ are the Pell sequence, then our sequence must be the sum of the first $n - 1$ terms of the Pell sequence (well, except possibly for an initial constant, which turns out to be one). And now you can look up or use standard linear recurrence methods to find out that the formula for $p_{n}$ is $p_{n} = \frac{(1 + \sqrt{2})^{n} - (1 - \sqrt{2})^{n}}{2 \sqrt{2}} .$

We are only interested in the long term behavior, so note that since the absolute value of $1 - \sqrt{2}$ is less than one, $(1 - \sqrt{2})^{n}$ goes to zero as $n$ grows without bound. Therefore we can ignore the second term in the numerator, and letting the constant $k = 1 / (2 \sqrt{2}),$ we have that $p_{n} \approx k (1 + \sqrt{2})^{n} .$ Therefore, $c_{n} \approx k \sum_{i = 0}^{n - 1} (1 + \sqrt{2})^{i} .$ But this expression is the sum of a geometric sequence, which has a convenient formula. So $c_{n} \approx k \frac{(1 + \sqrt{2})^{n} - 1}{(1 + \sqrt{2}) - 1} = \frac{(1 + \sqrt{2})^{n} - 1}{4} .$

This expression gives a very good picture of the long-term behavior of the first sequence $c .$ (With a little more work along these same lines — don’t ignore the small term in the numerator and be careful with all of the constants — one can actually obtain an exact closed-form formula for $c_{n} .$ )

Turning to the next challenge, involving subtraction, Jesse noted that the first few values of the $d$ sequence are 1, 2, 4, 7, 11, 16, 22, 29, 37, 46, … He then looked at the differences between successive numbers on this list, i.e., 2 – 1, 4 – 2, 7 – 4, and so on. That produced 1, 2, 3, 4, 5, 6, 7, etc. — a very familiar pattern! So the $d$ sequence must be related to the triangular numbers, which are the sums of the first $n$ natural numbers. The first six are 0, 1, 3, 6, 10, 15, so we can guess that each of the $d$ entries is one more than the corresponding triangular number. Since the formula for the $n$ th triangular number (starting from the first being 0) is $n (n - 1) / 2$ , we conclude that the formula we are looking for in this part of the problem is: $d_{n} = n (n - 1) / 2 + 1.$ And indeed we can check this formula by verifying that it satisfies the specified recurrence relation: $2 d_{n + 1} - d_{n} + 1 & = 2 + n (n + 1) - 1 - n (n - 1) / 2 + 1 = (n + 3 n) / 2 + 2 = (n + 3 n + 2) / 2 + 1 = (n + 1) (n + 2) / 2 + 1 = d_{n + 2} .$

About a year and a half after this Dilemma was originally proposed, PMP participant William Keehn sent in a successful approach to understanding the third sequence, $e_{n + 2} = e_{n + 1} \cdot (e_{n} + 2) / 2$ . He reasoned that when dealing with a lot of multiplication, it’s often helpful to take logarithms. In particular, because the number 2 appears twice in the recurrence for $e_{n}$ , William decided to use logs base two, and set $l_{n} = \log_{2} e_{n}$ (so that also $e_{n} = 2^{l_{n}}$ ). He calculated that the sequence of $l_{n}$ values starts $0, 1, 1.5849625 \dots, 2.5849625 \dots, 3.90689 \dots, 5.90689 \dots, 8.99435 \dots, 13.9485 \dots,$ and so on.

These numbers are looking very reminiscent of the familiar Virahāṅka-Fibonacci (VF) sequence $b_{n}$ mentioned in the statement of the problem. That resemblance turns out to be no surprise: if we take log base 2 of both sides of the recurrence for $e_{n}$ , we get $l_{n + 2} = l_{n + 1} + \log_{2} (e_{n} + 2) - 1.$ We still would like to get rid of the remaining $e_{n}$ in this expression to put it entirely in terms of the $l$ sequence, so we use a technique known as Standard Expert Trick #367: Add zero.

The key to using this trick is to find the right term to both add and subtract (in effect, adding zero) to simplify this expression. In our case, we would like an $l_{n}$ term, so we try adding $0 = l_{n} - \log_{2} (e_{n})$ to get $l_{n + 2} = l_{n + 1} + l_{n} - 1 + \log_{2} ((e_{n} + 2) / e_{n})$ . As $(e_{n} + 2) / e_{n} = 1 + 2 / e_{n} = 1 + 2^{1 - l_{n}}$ , we convert back to natural log to take advantage of the series expansion of $\ln (1 + x)$ near $x = 0$ : $l_{n + 2} & = l_{n + 1} + l_{n} - 1 + \frac{1}{\ln 2} \ln (1 + 2^{1 - l_{n}}) = l_{n + 1} + l_{n} - 1 + \frac{1}{\ln 2} (2^{1 - l_{n}} - 2^{1 - 2 l_{n}} + 2^{3 - 3 l_{n}} / 3 - \dots) .$

We can see from this expression and the initial values above that the $l_{n}$ are growing rapidly, like the VF series, so all of the terms in parentheses become large negative powers of two, and quickly become entirely negligible. In other words, as $n$ grows, $l_{n + 2} \to l_{n + 1} + l_{n} - 1$ . More directly, we observe that $l_{4} > b_{2} + 1$ and $l_{5} > b_{3} + 1$ , and that if $l_{n + 1} > b_{n - 1} + 1$ and $l_{n} > b_{n - 2} + 1$ , then $l_{n + 2} > l_{n + 1} + l_{n} - 1 > b_{n - 1} + 1 + b_{n - 2} + 1 - 1 = b_{n} + 1$ . So by induction, we conclude that for all $n > 3$ , $l_{n} > b_{n - 2} + 1$ . (Moreover, using the estimates above we can actually show that $l_{n} \to b_{n - 2} + 1$ as $n$ grows.) In any case, converting back to the original series, we have our lower bound (which turns out to be very close in the long run): $e_{n} > 2^{b_{n - 2} + 1} .$

Jesse Waite cracked the fourth sequence. Examining the first several terms was again the key: they are 1, 2, 6, 12, 16, 19, 22, 25. etc. In this case, the successive differences seem to be settling down to always be equal to three. And looking at the recurrence verifies this: once two successive entries $f_{n}$ and $f_{n + 1}$ are at least seven and differ by three, then $f_{n + 1} / f_{n}$ is between 1 and 1.5. Therefore $2 f_{n + 1} / f_{n}$ is between 2 and 3, which means $f_{n + 2} = 3 + f_{n + 1}$ , and so the next pair also differ by three (and are still at least seven) and the pattern continues. Hence, as Jesse concluded, $f_{n} = 3 n + 1$ for $n > 4$ .

We are now in a position to answer the final question of Dilemma 4: which sequence grows the slowest? Looking at all the expressions we derived, $c_{n}$ grows exponentially. Multiplying out the exact formula $d_{n} = n^{2} / 2 - n / 2 + 1$ shows that it grows quadratically. Except for a few terms at the beginning, $f_{n}$ is linear. And since the VF sequence itself grows exponentially, $e_{n}$ is the monster of the lot and grows double-exponentially.

Of these, division produces the slowest-growing sequence. To be sure, PMP participant Robert Noll sent a letter pointing out (a) guessing that division leads to slow growth would have been a good bet right from the start, and (b) we didn’t need an asymptotically correct formula for $e_{n}$ to see that it couldn’t be the slowest growing: It is very easy to prove the much weaker lower bound that $e_{n} > 2^{n - 2}$ , which already makes it grow faster than any quadratic function, let alone linear.

Nevertheless, in figuring out at least decent approximations for each of these series, and exact formulas where possible, we encountered many different problem-solving techniques. That’s a lot of mileage from just the four basic arithmetic operations!

January 30, 2022

Main Maker