Automatically Finding Recurrence Relations from Integer Sequences

In a lot of the recreational math and computer science problems I solve, I try to derive a recurrence relation that describes the situation. These recurrence relations pop up pretty often in counting problems (how many ways can you tile a 2xn grid with 2x1 tiles?) In some cases, I am unable to derive a recurrence relation directly from the problem statement, but still suspect that there exists some recurrence relation. In these cases, I end up solving the problem usin g brute force methods for small input sizes and analyzing/extrapolating the pattern. However, when the relation is obscure, it becomes hard to find.

In order to make this process easier in the future, I created a program that can automatically find recurrence relations for arbitrary integer sequences. To use it, simply type in the first few terms of a sequence you are interested in, and it will try to find a recurrence relation for that sequence. There are some constraints on the allowable inputs/outputs which I discuss below.

What this tool can be used for:

  • Finding linear recurrence relations with integer coefficients.
  • Finding linear recurrence relations of fixed order: $f(n)=k_1 f(n−1)+...+k_j f(n−j)$ for fixed j.
  • Finding recurrence relations for polynomials (like $n^2$) Finding recurrence relations for exponentials (like $2^n$).

What this tool can't be used for:

  • Finding recurrence equations involving real numbers.
  • Finding recurrence relations with unbounded order: $ f(n) = \sum_{i=1}^{n-1} i \cdot f(i) $.
  • Finding non-linear recurrence relations: $ f(n) = f(n-1) \cdot f(n-2) $

Limitations 

In general, this program works nicely for most recurrence relations. There are some things to watch out for, however. For example, if the coefficients are $0$, they are not displayed in the general formula. In some cases, the last term the recursive part of the relation has a coefficient of $0$. In these cases, the formula will hold for most terms of the sequence, but will look like it's erroneous for the first term.

To effectively use this program, you must provide enough terms of the sequence. For a recurrence relation of order $k$, you have to provide at least $k+2$terms so the program can find a relation and validate it at least once. The more terms you give, the more confident you can be that the recurrence relation is correct.

For performance reasons, you might not want to enter in massive sequences, as the underlying solver could be time consuming.

Conclusion 

This was a fun problem to work on and it was a good opportunity for me to explore the powerful functionality of sage, which is doing all the underlying mathematics. In a future blog post, I might elaborate on the mathematics that went into solving this problem, but for now if you're curious you can just view the source of this page and extract the sage code.

Comments

Post a Comment

Popular posts from this blog

Efficiently Remove Duplicate Rows from a 2D Numpy Array

Multi-Core Programming with Java

Beat the Streak: Day Three