# How to come up with a recurrence relation?

In general what are some things you can do to come up with a recurrence relation for something? I've had it covered in a course in combinatorics that I took, but our professor would always say "you just have to be clever".

So can there be a strategy to approach solving recurrence relations? Or is it really just kind of intrinsically knowing what to do....

-
Neither strategy nor just knowing what to do, but experience. The more of them you've seen done, the more ways you've seen to do them, the more techniques you have available to you when one comes along. – Gerry Myerson Nov 5 '12 at 6:17
there must have been something that the first person who came up with a recurrence relation for something did right? – Ethan Nov 5 '12 at 6:26
If you want to be the first person to come up with something, that's a different question. Nobody knows how to do that. – Gerry Myerson Nov 5 '12 at 11:31

Coming up with a recurrence relation and solving an already-found recurrence relation are two very different things. There are methods around for solving recurrence relations (and have been discussed on this site quite a lot), so I'll answer the other question: How to come up with a recurrence relation?

Often it requires some level of creativity (and knowledge of where the sequence comes from), and there's probably no general answer to this question. However, if you can't think of a clever way, perhaps one of these methods would be helpful.

• Enter the sequence into Sloane's On-Line Encyclopedia of Integer Sequences™ (and, if required, the "Superseeker" facility). Often you'll find useful formulae right away, along with references to work on the topic.

• If you know a large number in your sequence, then we can Google it. For example, if we knew the sequence contains 35148882404966400, then we can Google that number, and find very few webpages containing it.

• Try to fit a linear homogeneous recurrence to your sequence. In this case, we try to guess a recurrence relation satisfed by the sequence. For example, we guess $$s_{n+1}=as_n+bs_{n-1}$$ for all $n \geq 2$. Here we solve a system of linear equations: \begin{align} s_3 & = as_2+bs_1, \\ s_4 & = as_3+bs_2, \\ \vdots & \\ s_{k+1} & = as_k+bs_{k-1}. \\ \end{align} If no solutions exist, then you now have a formal proof that your sequence does not fit a linear homogeneous recurrence relation of the depth you tested. If a solution exists, then your guess is consistent with the sequence provided. It's best if you know a lot of terms in the sequence, so you can solve an overdetermined system. In this case, if a solution exists, this implies there is redundancy in your formula (and so your formula has "correctly predicted" values).

A more advanced version of the above, is fitting a linear recurrence with polynomial coefficients; this is known as Sister Celine's method (see Wikipedia or a paper by Doron Zeilberger for more details).

Comment: If you don't have enough terms, try to compute more. Often computer algebra systems are excellent at this -- they are relatively user friendly, and while not as fast as lower-level languages, they are typically quite fast (and if you use one that supports arbitrary precision arithmetic, you don't need to worry about rounding error). This will allow you to more easily use the three methods above, or, at least, find that they weren't helpful.

-

Some recurrences "build themselves" if you

1. consider cases and
2. read the terms out loud.

An example will clarify what I mean.

Let $a(n)$ be the number of binary strings of length $n$ that do not have two consecutive 0's. There are two cases: either the string begins with a 0 or it begins with a 1.

If the string begins with a 0, we know something more about the string: the next digit cannot be a 0. So, the first two digits are "01", and the rest of the string can be any properly formatted (meaning without two consecutive 0's) string of length $n-2$. There are exactly $a(n-2)$ of these, because reading this term out loud means "the number of properly formatted strings of length $n-2$".

If, instead, the entire string begins with a 1, we know nothing more about it except that the remaining $n-1$ digits must be properly formatted. There are exactly $a(n-1)$ of these, because reading this term out loud means "the number of properly formatted strings of length $n-1$".

Since the two cases were disjoint and account for all possible properly formatted strings, we can add them together to get the recurrence $$a(n) = a(n-2) + a(n-1).$$

-