How to find a general formula for any number sequence? $19,25,45,87,159$

Question

Suppose I have the following number series : 19,25,45,87,159

I want to build a formula for the nth term of the series.

Please help me with some algorithm which would solve my problem.

I tried to construct a generating function but i failed.

Answer 1

Hint: $$a_1=19$$ $$a_2=a_1+2\cdot3=25$$ $$a_3=a_2+4\cdot5=45$$ $$a_4=a_3+6\cdot7=87$$ $$a_5=a_4+8\cdot9=159$$

The recurrence formula is given by $$a_{n+1}=a_n+2n\cdot(2n+1)=a_n+4n^2+2n,n>1$$ Now you can proceed to find a direct formula for $a_n$

The following terms are:$$19, 25, 45, 87, 159, 269, 425, 635, 907, 1249, 1669, 2175, 2775, 3477, 4289, 5219...$$

Speaking of a general algorithm, I don't think there is one. To show this, let's take the square root of any nonsquare number, $\sqrt7=2.6457513 $ for example... And then we construct a sequence in which $a_n$ is nth digit after the decimal point. How can we ever extrapolate a general formula in reverse if we don't know that we are taking square root of 7 in the first place?

Also, as David said, for any finite sequence you can have infinitely many different closed-form formulas which give all the correct values you have, but diverge later on. That defies a general formula when you can only observe finite many terms of an unknown sequence.

Answer 2

There is a general approach called "Lagrange polynomial" which ensures that there exists a polynomial of finite degree that passes all given finite plots $(x_i, y_i)$ (with distinct $x_i$s). Thus, we can set a polynomial $f$ for a given sequence $\{a_i\}_1^n$ that matches $f(i) = a_i$ for $i=1,2,\cdots,n$.

The strategy is not difficult. Let \begin{equation}p(x) = (x-1)\cdots(x-n)\end{equation} and $\displaystyle{p_i(x)= \frac{p(x)}{(x-i)}}$. If $i \neq j$, then $p_i(j)=0$. So, for $\displaystyle{q_i(x)=a_i\frac{p_i(x)}{p_i(i)}}$, $q_i(i)=a_i$ and $q_i(j)=0$. Thus, $\displaystyle{L(x) = \sum_1^n q_i(x)}$ is a desired polynomial.

For more details: https://en.m.wikipedia.org/wiki/Lagrange_polynomial