Guessing Closed Formulas for Recursively Defined Sequences

Why One Might Want a Closed Formula Instead of a Recurrence Relation

Suppose we have a sequence \(\{a_n\}_{n=1}^\infty\) defined recursively with initial conditions \(a_1=1\), \(a_2=1\), and recurrence relation \(a_n=a_{n-1}+a_{n-2}\). Suppose also that someone asked you to find the value of \(a_{2351}\). In order to do that, based on the rule given, we need to compute

$$\begin{align}a_{2351}&=a_{2350}+a_{2349}\\&=(a_{2349}+a_{2348})+(a_{2348}+a_{2347})\\&=\ldots\end{align}$$

And so on. In the above, we need to compute the previous sequence values to get the current one… but to do that we need to compute each of those previous values’ previous values, and so on. Not too much joy in that. Alternatively, one could generate the sequence out to the \(2351\)st location… Sounds like a lot of work that nobody wants to do. So what can we do?

It would be nice if there was a closed formula that would tell us what the \(2351\)st element of the sequence was. That would allow us to compute \(a_{2351}\) without needing to compute all of the elements of the sequence that came before the \(2351\)st one.

In the Fibonacci Sequence given above, the closed formula is given by

$$\begin{align}a_n&=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right].\end{align}$$

Still not pretty, but a lot more convenient if you want to compute the \(2351\)st element of the Fibonacci Sequence, \(a_{2351}\). Just plug in \(n=2351\) into the formula and hope that your calculator can handle the result!

$$\begin{align}a_{2351}&=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{2351+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{2351+1}\right]\\&=9.5599853231642818235778509… \cdot 10^{490}\end{align}$$

which is a lot more than the number of atoms estimated to be in the observable universe.

Guessing Closed Formulas from Recursively Defined Sequences

Certainly, the above method is far from scientific, but it does help your pattern recognition skills to do things this way.

Using the Iteration Method to Find Closed Formulas for Recursively Defined Arithmetic Sequences

Example: Let \(\{a_n\}_{n=0}^\infty\) be defined by the initial condition \(a_0=5\) and recurrence relation \(a_n=a_{n-1}+3\) for all \(n\geq 1\). Guess a closed formula for \(a_n\).

Essentially, we just compute \(a_1\), \(a_2\), \(a_3\), etc. showing all work, in hope that we will see a pattern allowing us to find a closed formula.

So, in the above, we computed everything but the final answer number for each of \(a_1\), \(a_2\), \(a_3\), etc. We noticed that there was a pattern developing on the right-hand-side of the equation, namely that if we were trying to compute, say \(a_3\), we noticed that we had \(5\) plus 3 \(3\)’s being added together. Similarly for \(a_4\) or \(a_5\), where we had \(5\) plus 4 or 5 (respectively) \(3\)’s being added together. So, assuming that this pattern persists, for \(a_n\), no matter what \(n\) is, we will probably have \(5\) plus \(n\) \(3\)’s added together. Thus, we can guess the formula

$$\begin{align}a_n&=5+3n\end{align}$$

**Notice that we don’t compute the final value of each \(a_i\) (like computing \(a_1=8\) for \(n=1\), \(a_2=11\) for \(n=2\), etc.). Doing so would not help us see a pattern develop within the computations. So, it is usually best just to write things out to a point where you have a bunch of numbers added, subtracted, multiplied, etc. like what we have on the right-hand-side of each of the above equations.

Note that the above approach used to go from recursive definition to a closed formula is not something special that only works for recursively defined arithmetic sequences. It can be used for a litany of different types of sequences. Next, we show how to use this iterative method to find a closed formula for recursively defined geometric sequences.

Using the Iteration Method to Find Closed Formulas for Recursively Defined Geometric Sequences

Example: Let \(\{a_n\}_{n=0}^\infty\) be a recursively defined sequence with initial condition \(a_0=3\) and recurrence relation \(a_n=a_{n-1}\cdot 2\). Guess a closed formula for \(a_n\) by iteration.

As before, we write out the first several entries of the sequence and see if we can notice a pattern in how the entries are computed.

So, in the above, we computed everything but the final answer number for each of \(a_1\), \(a_2\), \(a_3\), etc. We noticed that there was a pattern developing on the right-hand-side of the equation, namely that if we were trying to compute, say \(a_3\), we noticed that we had \(3\) times 3 \(2\)’s being added together. Similarly for \(a_4\) or \(a_5\), where we had \(3\) times 4 or 5 (respectively) \(2\)’s being multiplied together. So, assuming that this pattern persists, for \(a_n\), no matter what \(n\) is, we will probably have \(3\) times \(n\) \(2\)’s multiplied together. Thus, we can guess the formula

$$\begin{align}a_n&=3\cdot 2^n\end{align}$$

Again, on the right-hand-side of each of the equations above, we did not compute the final value for each of \(a_1\), \(a_2\), \(a_3\), etc. We ended each line with a product of numbers to help us see the pattern from line to line. That is what allows us to determine a closed formula for the sequence.