**Observation**: If we take the graph with two vertices, A and B, with a loop {A,A} and undirected edge {A,B}, then the number of closed walks $W_n$ of length $n \geq 1$ starting from A we get $W_1=1$ (counting AA), $W_2=2$ (counting AAA and ABA) and $W_n=W_{n-1}+W_{n-2}$, i.e. the Fibonacci numbers.

Question: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?More generally, which types of recurrences can be realised as the number of walks of some type in some graph?

If we can interpret a recurrence relation as the number of walks in a graph in some way, then might be able to use spectral theory to find formulas for the sequence. (see: Frank Harary and Allen J. Schwenk, The spectral approach to determining the number of walks in a graph. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)

regular languagesaccepted by a Nondeterministic Finite Automaton. (see my comment below Qiaochu Yuan's answer on this page) $\endgroup$ – sleepless in beantown Oct 30 '10 at 8:02