Obtaining recurrence relation from a given sequence

[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.

 

[Greg Bernhardt]

I'm sorry you are not finding help at the moment. Is there any additional information you can share with us?

 

[pasmith]

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)?

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