-1
$\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$
9
  • 7
    $\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$ Commented May 8, 2018 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
    Commented May 8, 2018 at 3:29
  • $\begingroup$ Can You show me the steps please? $\endgroup$
    – David
    Commented May 8, 2018 at 3:29
  • 4
    $\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
    Commented May 8, 2018 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$
    – JRN
    Commented May 8, 2018 at 4:45

2 Answers 2

2
$\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$
4
  • $\begingroup$ The terms may not be in the form of a polynomial evaluated at positive integers... $\endgroup$
    – Macrophage
    Commented May 8, 2018 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
    Commented May 8, 2018 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
    Commented May 8, 2018 at 3:55
  • $\begingroup$ Oh, I understood what you meant by. $\endgroup$
    – Junho Han
    Commented May 8, 2018 at 4:03
0
$\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$
10
  • $\begingroup$ I got this from computer: a(n) = 1/3 (4 n^3 - 3 n^2 - n + 57) $\endgroup$
    – David
    Commented May 8, 2018 at 3:35
  • $\begingroup$ Thank you for the answer, but my question was to find an algorithm for any such sequence. $\endgroup$
    – David
    Commented May 8, 2018 at 3:36
  • $\begingroup$ That cubic term makes sense! But I don't think there is an algorithm for any arbitrary sequence... $\endgroup$
    – Macrophage
    Commented May 8, 2018 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
    Commented May 8, 2018 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
    Commented May 8, 2018 at 3:49

Not the answer you're looking for? Browse other questions tagged .