Obtaining recurrence relation from a given sequence

1. Sep 8, 2014

mnb96

Hello,

it is known that given a certain recurrence relation that describes a sequence of numbers, it is often possible to obtain a function f[n] that directly yields the n-th number of the sequence. This is usually accomplished by using powerful techniques involving generating functions or the Z-transform (see for instance this thread).

My question is: are there equally powerful techniques that allow one to do the reverse, i.e. given the closed-form f[n] of a sequence, obtain one possible recurrence relation that describes the same sequence (even approximately)?

I am mot sure this is the right forum, but at least I see an analogy between Laplace transform and Z-transform and between the above problem and its continuous analog, i.e. given a certain function f(x), find a differential equation for which f is a solution.

2. Sep 16, 2014

Greg Bernhardt

Trivially, if $x_n = f(n)$, then $$x_{n+1} = x_n + f(n+1) - f(n)$$ is one such recurrence relation.