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

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.

I tried to construct a generating function but i failed.

• Declare that the full sequence is $$19,25,45,87,159,0,0,0,0,0,\ldots$$ and you can write down a simple formula involving Iverson brackets or Kronecker deltas. – hmakholm left over Monica May 8 '18 at 3:22
• @Henning Makholm The full sequence is 19, 25, 45, 87, 159, 269, 425, 635, 907, 1249, 1669, 2175, 2775, 3477, 4289, 5219. – David May 8 '18 at 3:29
• Can You show me the steps please? – David May 8 '18 at 3:29
• To restate (what I think is) @HenningMakholm's comment, questions of this form are ambiguous. There are many sequences starting that way, so you haven't given enough information for us to know which you have in mind. Presumably you want a "simple" such sequence, but in general simplicity is subjective (in this particular case Macrophage gives a defensible candidate). – stewbasic May 8 '18 at 3:44
• 19, 25, 45, 87, 159, 269, 425, 635, 907, 1249, 1669, 2175, 2775, 3477, 4289, 5219, 0, 0, 0, 0, 0, ... – Joel Reyes Noche May 8 '18 at 4:45

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.

• I got this from computer: a(n) = 1/3 (4 n^3 - 3 n^2 - n + 57) – David May 8 '18 at 3:35
• Thank you for the answer, but my question was to find an algorithm for any such sequence. – David May 8 '18 at 3:36
• That cubic term makes sense! But I don't think there is an algorithm for any arbitrary sequence... – Macrophage May 8 '18 at 3:37
• Okay let me ask a new question regarding that topic. By the way, dont you think that interpolation would work for any arbitary sequence? – David May 8 '18 at 3:40
• Nice Argument, but 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. – David May 8 '18 at 3:49

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

• The terms may not be in the form of a polynomial evaluated at positive integers... – Macrophage May 8 '18 at 3:44
• Which terms do you point out? Lagrange polynomial may not be the best generating function for fitting a given sequence. – Junho Han May 8 '18 at 3:51
• I mean the general term, it may not be that prescribed by the polynomial. As we can only fit with finite many terms. – Macrophage May 8 '18 at 3:55
• Oh, I understood what you meant by. – Junho Han May 8 '18 at 4:03