The Prisoner's Dilemma

One of the great things about mathematics is that it’s always possible to look again at familiar things and discover something new. Sometimes these discoveries 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. Putting that in symbols would correspond to $b_n=b_{n-1}+b_{n-2}$. The sum recurrence begins with 1, 2, 3, 5, 8, …, and continues with each additional entry equal to the sum of the previous two.

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.

Aside: Long-term behavior

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

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\cdot 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)\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 will be accepted through 2022 May 27.