Extension: Harder Sequences and Patterns

Introduction to Recognizing Recurrences:

Recurrences refer to a class of problems that share one trait in common: every instance of a recurrence is deterministically related to smaller instances of the same recurrence.

Here is a task for you. Pretend you are a priest in a demon's temple. There are 3 slabs — A, B and C — in the temple and you have a stack of 256 disks placed on slab A, each one of a different size and the disks stacked in decreasing order of size (the largest one placed at the bottom, the next largest one on top of that and so on). Your objective is to awaken the demon king by transferring the tower of disks from slab A to slab C. But wait, there are some constraints imposed on what you can do.

1. You can only move one disk at a time.

2. You can only move a disk that is on the top of a stack.

3. You cannot, at any time, place a larger disk on a smaller one.

You may place disks on slab B during the process of making these shifts.

But 256 is a large number, so you initially want to have an idea of how long this is going to take you. If you cannot accomplish this thing in a lifetime, you would much rather spend your life doing math.

Now you are probably thinking: "If the answer is $\it{10^{77}}$, how on Earth am I supposed to compute that in any reasonable time span. I gave up drawing diagrams of the shifts and simply bashed the options."

The answer to this lies in the power of recurrences.

It starts with a very powerful observation. Moving 256 disk to slab C is equivalent to moving the upper 255 disk from slab A to slab B, the lowest and largest disk from slab A to slab C, and then all the 255 disks from slab B to slab C. In other words, if you know how many steps it would take to move 255 disks, the problem is reduced to something that is actually surmountable by human beings.

Here is some intuition as to why you can't do it faster. You know that you must move the lowest disk from A to C and you require at least one step to do so. And you need to transfer the upper $255$ disks to slab B if you want to move the largest disk from slab A to slab C (A and C must be clear for the step to happen). Now, you need to transfer the $255$ blocks from B to C to complete the process.

The answer is intuitive in that the set of $n-1$ disks is moved twice. And there is a single lone shift of the largest block.

We can write the number of steps it takes to move 256 blocks in the following form.

$$S_{256}=2S_{255}+1$$

While a lot simpler, this form is still not very helpful, since $S_{255}$ is $2S_{254}+1$ and it is going to be boring to expand this for the rest of time. What every recurrence needs is a base case. That is, a predefined answer for a small version of the problem, which is to ensure we don't expand a recursive equation (like the one for $S_{256}$ for eternity).

And in addition to a base case, we need is some enlightenment in a closed form solution. A closed form solution is a simple equation that gives you the value of $S_{n}$ as a function of $n$. We think that if we find a closed form solution, we can directly plug $256$ into our solution and obtain the answer outright.

Thinking Small:

Now we have fixed our base case. From the base case, we can extrapolate $S_{n}$ infinitely.

$S_1=2S_0+1=2\times 0 + 1 = 1$

$S_2 = 2S_1 + 1 = 3$

Similarly:

$S_3 = 7$

$S_4 = 15$

Play with it a bit more and see if you notice a pattern?

There is indeed a neat closed form solution for the recurrence and we can verify this by plugging in $2^n$ into the original recursive equation and checking if it works.

$$\begin{align} S_n&=2S_{n-1}+1\\ S_n&=2\times (2^{n-1}-1)+1\\ S_n&=2^n-2+1\\ S_n&= 2^n - 1\\ \end{align}$$

We can check that the closed form solution works for $S_0$. Since it works for the base case, it works for all subsequent cases.

However, we relied on a lucky guess to determine the closed form solution. We can't count on clairvoyant abilities when recurrences get more complex.

We will try to find a neat way to determine the closed form solution of a recurrence.

Let us go back to the original recursive equation. $$\begin{align} S_n&=2S_{n-1}+1\\ S_n+1&=2S_{n-1}+2\\ S_n+1&=2(S_{n-1}+1) \end{align}$$

At this point we can define a new recurrence function given by $$L_n = S_n + 1$$

Hence $L_n = 2L_{n-1}$. $L_0 = 1$. After this, it is straightforward that $L_n = 2^n$. $$S_n = L_n - 1$$ $$S_n = 2^n - 1$$

So we did find the closed form solution without guessing! The reason that the study of recurrences is one that attracts a lot of attention in mathematics is that there are ways of finding closed form solutions without being a clairvoyant: such as a generating functions.

Returning to our earlier case of the priest, we have that $S_{256}=2^{256}\approx 10^{77}$. If you worked at $1$ step per nanosecond, the entire process would take you $3\times 10^{60}$ years. Yes, do give up priesthood for your own good.

To summarize what a recurrence is, it is a system that is governed by previous instances of the system, and can be described by two pieces of data: a base case and a recursive equation. And the recursive equation derives all values of the recursion from the base case.