I know how to find a non-recursive formula for a recursively defined sequence. However, now I have this puzzle which gives me a sequence (but not the recursive definition) and challenges me to find the next item. What are basic steps I can take to try to find a recursive definition of some beginning of a sequence?
For example, we could've been given the beginning of a sequence $a_0,a_1,a_2,\ldots=1, 4, 9, 16, \dots$ and the challenge being to find the next item, for example, $a_4=25$. This sequence could be recursively defined as
$$a_n = \begin{cases}1&\text{if $n=0$}\\a_{n-1}+2n-1&\text{if $n>0$}\end{cases}$$
or in closed form as $a_n=(n+1)^2$.
However, say we don't see a logic behind the sequence. Is there a way we can find any of the two forms for the sequence (either recursive or closed-form) by clever guessing, or applying some trick, assuming such a form exists?
Note: I intentionally didn't mention the sequence in my puzzle; it would be cheating, and I want to do it myself.
Best Answer
As mentioned in the comments, there is no way to find a defining formula for a infinite sequence from a finite initial segment because given any finite list there are infinitely many ways to extend it.
That said, if you know ahead of time that the mystery sequence is defined by some recurrence and you know something about the structure of that recurrence, you can discover its formula.
For example: Given $a_0=1, a_1=4, a_2=9, a_3=16, \dots$ and the knowledge that our recurrence is a of the form $a_{n}=ba_{n-1}+cn+d$, we get that:
$$4=b(1)+c(0)+d, 9=b(4)+c(1)+d, \mbox{ and } 16=b(9)+c(2)+d$$
Thus $b+d=4$, $4b+c+d=9$, $9b+2c+d=16$.
Solving this (linear) system yields $b=1$, $c=2$, and $d=-1$. So that $a_n = a_{n-1}+2n-1$.
This is essentially the same process as polynomial curve fitting.
The main problem with all of this is knowing what your formula should look like to begin with. Without making some assumption about the shape of your formula, solving such a problem is hopeless (because the problem is ill defined).