If infinitely many points of a sequence are given, is it possible to find out the recurrence relation?

Question

I was thinking about sequences and stumbled upon a concept. If infinitely many points of a sequence are given, is it possible to find out the recurrence relation?

Please enlighten.

Answer 1

If a sequence has a recurrence (say $a_{n + k} = f(n, a_n, \ldots, a_{n + k - 1})$, you can construct an infinitude of recurrences for it, e.g. by constructing one for $a_{n + k + 1}$ like $a_{n + k + 1} = f(n + 1, a_{n + 1}, \ldots, a_{n + k - 1}, f(n, a_n, \ldots, a_{n + k - 1}))$ and so on.

For each sequence $a_n$ you have the (trivial) recurrence $a_n = f(n)$.

Answer 2

The recurrences \begin{align*} a_0 &= 1 \\ a_{n+1} &= a_n \end{align*} and \begin{align*} b_0 &= 1 \\ b_{n+1} &= b_n^2 \end{align*} generate the same sequence of values. Are they the same recurrence?