2
$\begingroup$

consider the sequence of numbers below,

2 5 10 18 31 52 . . .

the sequence goes on like this.
My Question is,
How to find the nth term in the sequence?
thanks.

$\endgroup$
3
  • $\begingroup$ There was a similar question posted here, look at this link : math.stackexchange.com/questions/251406/… $\endgroup$
    – pritam
    Dec 29, 2012 at 7:31
  • $\begingroup$ Looking at the finite differences can also be useful. Looking at the first few orders can tell you if the sequence is from a polynomial or an exponential or something. $\endgroup$ Dec 29, 2012 at 8:09
  • 1
    $\begingroup$ there is no one next number, anything can be made to fit some equation. $\endgroup$
    – jimjim
    Dec 29, 2012 at 10:37

7 Answers 7

3
$\begingroup$

One could try to stare at it for long enough and notice, that if one "demands" the first and the second term to be $2$ and $5$ respectively then the third term is $(2 + 5 + 3) = 10$ and similarly for the other terms.

After you have noticed that $a_{n+2} = a_n + a_{n+1} + 3$ you could try to solve it using generating functions.

To do so, multiply both sides with $x^n$ then sum both sides $\sum_{n \geq 0}$. Set $G(x) = \sum_{n \geq 0} a_n x^n$. After some manipulation and using that $\sum_{n \geq 0}x^n = \frac{1}{1-x}$ I arrived at $$ \frac{1}{x^2}( G(x) -a_0 - a_1x) = G(x) + \frac{1}{x}(G(x) - a_0) + \frac{3}{1-x}$$

And after some more manipulations and using $a_0 = 2$ and $a_1 = 5$ I arrived at $$ G(x) = - \frac{x + 2}{(1-x) (x^2 + x - 1)}$$

Now one would look up the corresponding power series to read off the $n$-th coefficient (which corresponds to the $n$-th term of your sequence) but for this one it seems that there isn't an easy power series which is somewhat disappointing. (For a list of potential power series check for example late H. S. Wilf's book on page 52/53).

Nonethelss, the mechanics I have outlined above work in a wide variety of cases so you might as well keep this approach in the back of your mind and use it when you need it to solve something else in the future.

$\endgroup$
5
  • 1
    $\begingroup$ Very good now. :-) $\endgroup$
    – Mikasa
    Dec 29, 2012 at 8:54
  • 1
    $\begingroup$ @BabakSorouh Of course, one (read: I) would have to be sure not to make any mistakes in the manipulations I mention in order to conclude that $G(x)$ isn't "easy". : ) $\endgroup$ Dec 29, 2012 at 8:57
  • 1
    $\begingroup$ Seems to be a sign error maybe? Your $G(x)$ as you have written it is $-\frac{x+2}{1-x^{3}},$ which has all $a_{n}$ negative. $\endgroup$ Dec 29, 2012 at 9:19
  • $\begingroup$ @GeoffRobinson Excellent, thank you. Will redo the computation. $\endgroup$ Dec 29, 2012 at 9:24
  • $\begingroup$ @GeoffRobinson There was indeed a sign error. Correcting it still doesn't seem to yield an easy $G(x)$ unfortunately. $\endgroup$ Dec 29, 2012 at 9:36
3
$\begingroup$

$$a_{n+2}=a_{n}+a_{n+1}+3, \; (n\in \mathbb{N})$$

$\endgroup$
2
$\begingroup$

This is listed at OEIS as A006327. Title of the sequence says:

a(n) = Fibonacci(n) - 3. Number of total preorders. (Formerly M1371)

$\endgroup$
1
  • $\begingroup$ Good for hunting down and killing a sequence! + $\endgroup$
    – amWhy
    Mar 1, 2013 at 1:00
1
$\begingroup$

It's usually a good start to consider any famous sequences you know and apply operations to them until a pattern pops out. In this case, consider the fibonacci sequence minus a constant.

$\endgroup$
1
$\begingroup$

Let the given sequence $S_n :\{2, 5 ,10, 18, 31, 52\}$

Taking differences, $S_n':\{3, 5, 8, 13,21\}$

Again taking differences, $S_n'':\{2, 3 ,5, 8\}$

Again taking differences, $S_n''':\{1,2,3\}$

If $T_r,T_r',T_r'',T_{r}'''$ be the $r$th terms of series $S_r,S_n',S_n'',S_{n}'''$ respectively.

Clearly, $T_r'''=T_{r+1}''-T_r''$ and $T_r'''=r$

So, $T_r''$ is of order $2,=Ar^2+Br+C$(say)

then $r=T_r'''=T_{r+1}''-T_r''=A(2r+1)+B=2Ar+A+B$

Comparing the coefficients of $r,2A=1\implies A=\frac12$

Comparing the constant terms, $A+B=0\implies B=-A=-\frac12$

$\implies T_r''=\frac{r^2-r}2+C, 2=T_1''=C\implies C=2\implies T_r''=\frac{r^2-r}2+2=\frac{r^2}2-\frac r2+2$

Again, $ T_r''=T_{r+1}'-T_r'$

So, $T_r'$ is of order $3,=Dr^3+Er^2+Fr+G$(say)

$\frac{r^2}2-\frac r2+2=T_r''=T_{r+1}'-T_r'=D\{(r+1)^3-r^3\}+E\{(r+1)^2-r^2\}+F\{(r+1)-r\}=3Dr^2+r(3D+2E)+D+E+F$

Comparing the coefficients of the different powers of $r,$ we get $D=\frac16,E=-\frac12,F=\frac73$ so that $T_r'=\frac16r^3-\frac12r^2+\frac73r+G$

Now, $3=T_1'=\frac161^3-\frac121^2+\frac73+G\implies G=1$

$\implies T_r'=\frac16r^3-\frac12r^2+\frac73r+1$

Again, $ T_r'=T_{r+1}-T_r$

So, $T_r'$ is of order $4,=Pr^4+Qr^3+RFr^2+Sr+T$(say)

$\frac16r^3-\frac12r^2+\frac73r+1= T_r'=T_{r+1}-T_r=P\{(r+1)^4-r^4\}+Q\{(r+1)^3-r^3\}+S\{(r+1)-r\}=4Pr^3+r^2(6P+3Q)+r(4P+3Q+2R)+P+Q+R+S$

Comparing the coefficients of the different powers of $r,$ we shall get the values of $P,Q,R,S$.

$T$ can be determined using the value of any term $T_r$ like the earlier case.

$\endgroup$
3
  • $\begingroup$ how you say T3=A(3)(2)+..., when Tn=A(n-2)(n-1)+.... $\endgroup$
    – yuv60
    Dec 29, 2012 at 7:40
  • $\begingroup$ @yuv60, is it ok,now? $\endgroup$ Dec 29, 2012 at 7:44
  • $\begingroup$ how about the fifth term... it gives 26 instead of 31.. $\endgroup$
    – yuv60
    Dec 29, 2012 at 7:53
1
$\begingroup$

There is no single answer, using Lagrange extrapolation one can make a polynomial were the next number is $0,1,-1,e^{i\pi},etc.$ of course some one once mentioned here the next number with the least entropy is the most natural answer but they didn't mention how to get it.

$\endgroup$
0
$\begingroup$

The sequence can be expressed in many ways.

As Matt N. and M. Strochyk mentioned: $$ a_{n+2}= a_{n}+a_{n+1}+3,$$ $$ a_1 = 2 \quad (n\in \mathbb{N})$$ Or as this one for example: $$ a_{n+1}= a_{n}+\frac{(n-1)n(2n-1)}{12}-\frac{(n-1)n}{4}+2n+1,$$ $$ a_1 = 2 \quad (n\in \mathbb{N})$$ It's interesting that the term: $$ b_n = \frac{(n-1)n(2n-1)}{12}-\frac{(n-1)n}{4}+2n+1$$ gives five Fibonacci numbers $(3, 5, 8, 13, 21)$ for $1 \leq n \leq 5$.

$\endgroup$

You must log in to answer this question.

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