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 Virahanka or Fibonacci sequence, in which you obtain each term by adding the previous term to the one before it, or $b_n = b_{n-1} + b_{n-2}$. The sum recurrence begins with 1, 2, 3, 5, 8, and so on.

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 \phi^{n+1}/\sqrt5$ for the sum recurrence, where $\phi = (1+\sqrt5)/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.

  1. 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.
  2. 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!)
  3. Half the product of the previous two terms. So in this case our next increment is 2·1/2 = 1, and the third term will be 3.
  4. Twice the quotient of the previous two terms. Now the next increment is (2/1)·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!

Update: (2022 Sep 15) Submissions have only been received related to sequences 1, 2, and 4 above. You can see the solution to the first one below, and the solutions to 2 and 4 will be posted as soon as the Fall 2022 PMP Newsletter is out. Therefore, submissions will still be accepted for the remaining sequence, number 3, through the deadline for the other new 2022 Fall problems.

This problem originally appeared in the Prisoner’s Dilemma in the 2022 Winter issue of the PMP Newsletter. Solutions will be accepted through 2022 Dec 31.

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,\ldots,$ its recurrence relation is $c_{n+2} = c_{n+1} + c_n – 1 + c_{n+1} = 2c_{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, \ldots$

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} = 2p_{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{split}c’_{n+2} & = c_{n+3} – c_{n+2} = 2c_{n+2} + c_{n+1} – (2c_{n+1} +c_n -1) \\ & = 2(c_{n+2}-c_{n+1}) + (c_{n+1} – c_n) = 2c’_{n+1} + c’_n,\end{split} \] 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+\sqrt2)^n-(1-\sqrt2)^n}{2\sqrt2}.\]

We are only interested in the long term behavior, so note that since the absolute value of $1-\sqrt2$ is less than one, $(1-\sqrt2)^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\sqrt2),$ we have that $p_n\approx k(1+\sqrt2)^n.$ Therefore, \[ c_n\approx k\sum_{i=0}^{n-1} (1+\sqrt2)^i.\] But this sum is geometric, which has a convenient formula. So \[c_n\approx k\frac{(1+\sqrt 2)^n-1}{(1+\sqrt2)-1} = \frac{(1+\sqrt2)^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.$)

Dilemma