-2
$\begingroup$

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.

$\endgroup$

closed as primarily opinion-based by Carl Mummert, Namaste, zz20s, Mohammad Riazi-Kermani, Arnaud D. May 8 '18 at 20:57

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 5
    $\begingroup$ 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. $\endgroup$ – Henning Makholm May 8 '18 at 3:22
  • $\begingroup$ @Henning Makholm The full sequence is 19, 25, 45, 87, 159, 269, 425, 635, 907, 1249, 1669, 2175, 2775, 3477, 4289, 5219. $\endgroup$ – David May 8 '18 at 3:29
  • $\begingroup$ Can You show me the steps please? $\endgroup$ – David May 8 '18 at 3:29
  • 3
    $\begingroup$ 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). $\endgroup$ – stewbasic May 8 '18 at 3:44
  • 2
    $\begingroup$ 19, 25, 45, 87, 159, 269, 425, 635, 907, 1249, 1669, 2175, 2775, 3477, 4289, 5219, 0, 0, 0, 0, 0, ... $\endgroup$ – Joel Reyes Noche May 8 '18 at 4:45
1
$\begingroup$

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.

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

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

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.