Given a random sequence give a recurrence defining it.

Question

I heard that there's some hard way to mechanically obtain a recurrence relation for a given sequence. Do you know something about it/where can I find information about it?

Answer 1

Recurrence relations come in all shapes and sizes. You're probably familiar with $n!$ or the Fibonacci numbers being described as recurrence relations. But, there are some bizarre ones out there. For example:

• The look-and-say sequence starts with $1$ and subsequent terms in the sequence are determined by "reading" the previous term.

We are limited only by our imaginations in finding bizarre (and perhaps highly contrived) recurrence relations.

Now imagine we were given some bizarre and highly contrived sequence generated by a recurrence relation, but we have forgotten the recurrence relation and want to recover it. There is basically no hope whatsoever of doing so (nor would there be much point).

Further, we can only look at a finite number of terms in a given sequence. Given that finite number of terms, we could fit an infinite number of (even linear homogenous) recurrence relations to them: If we know $(a_i)_{i=1}^N$, then we define a sequence $(x_i)_{i \geq 1}$ recursively by $$x_i=\begin{cases} a_i & \text{ for } i \in \{1,2,\ldots,N\}; \\ c & \text{if } i=N+1 \text{ (for any } c \in \mathbb{R} \text{)}; \\ \sum_{i=n-N-2}^{n-1} x_i & \text{otherwise.} \end{cases}$$ We get an infinite number of recurrence relations by the choice of $c$. So, in practice, even in one of the simplest cases (linear homogeneous recurrence) it is not possible to go backwards from an infinite sequence to a recurrence relation.

That being said, there are ways to "guess" a recurrence given the first few terms in a sequence.

To illustrate, the first few Fibonacci numbers are $1$, $1$, $2$, $3$, $5$. We could guess there's a linear homogeneous recurrence for this sequence of the form $a_{n+1}=c a_n + d a_{n-1}$. We check to see if this works:

• We see $1,1,2$ occur sequentially, so, if $a_{n+1}=c a_n + d a_{n-1}$ is correct, then we must have $2=c+d$.

• We see $1,2,3$ occur sequentially, so $3=2c+d$.

• We see $2,3,5$ occur sequentially, so $5=3c+2d$. (We could keep going if we like.)

So, we have a system of equations: $$ \left(\begin{matrix} 1 & 1 \\ 2 & 1 \\ 3 & 2 \\ \end{matrix}\right) \left(\begin{matrix} c \\ d \\ \end{matrix}\right) = \left(\begin{matrix} 2 \\ 3 \\ 5 \\ \end{matrix}\right) $$ which we solve to find $c=1$ and $d=1$. So our guess is that the recurrence is $a_{n+1}=a_n + a_{n-1}$. But we can't know for sure without knowing that the sequence is indeed the Fibonacci sequence (and we can't know that without inspecting all infinitely many terms, or the recurrence relation defining these numbers [or something equivalent]).