5

I'm by no means advanced at mathematics, but I'm trying to figure out a formula to get the nth value of the following sequence: $1,4,10,20,35,56,84$.

I'm using 'difference' tables to try and come up with a formula and I'm currently at the $n$-th term: $$n^3-5n^3+25n^3-125n^3+625n^3+3750n^3+22500n^3+135000n^3+810000n^3+4860000n^3$$

I'm not sure if I'm using a bad method, or if I've gone wrong somewhere but it just seems like the number I'm multiplying by n is increasing with no sign of levelling out.

If I continue to use a difference table will I eventually reach a formula or is it possible this number will just continue to increase infinitely?

Tomas
  • 4,534
Ant
  • 53
  • 3
    Difference table works nicely (in this case). Note that first differences are $3,6,10,15,21,28$, maybe already familiar. Second differences are very familiar. – André Nicolas Jun 27 '13 at 22:31
  • So I get the 3rd difference is 1. So then I get

    nth term - $n^3$

    Running that through the table again I get 5 as the common difference after 3 iterations. Giving me $5*n^3$. Is that correct?

     – Ant Jun 27 '13 at 22:39
  • 1
    There is a posted answer that contains a large hint. In principle you can find the coefficients of $n^3$, $n^2$, $n$, and the constant term by solving $4$ linear equations in $4$ unknowns. In practice you can do it faster. And if you are familiar with the Pascal Triangle a simple answer will leap out. – André Nicolas Jun 27 '13 at 22:44
  • 1
    I highly recommend the 2nd best website ever, The On-Line Encyclopedia of Integer Sequences® (OEIS®), oeis.org –  Jun 28 '13 at 01:31
  • @Ant like Oleg's answer suggests below, if the first differences don't give you the answer then take the second differences and so on a few more times. The $n$-th order differences being constant means a $n-1$ degree polynomial (which has $n$ terms) is what you are looking for. – Fixed Point Jun 28 '13 at 01:55
  • Of course, the complete sequence goes as this: $1,4,10,20,35,56,84, 42, 42, 42, 42, 42, \ldots$ ;-) The rule is as follows: If $a(n-1)$ is a multiple of $42$, $a(n)=42$. Otherwise, $a(n)$ is the n-th tetrahedral number. – celtschk Jun 28 '13 at 16:04

4 Answers4

7

Difference table looks like

\begin{array}{|c|c|c|c|} 1 &\\ & 3 &\\ 4 & & 3\\ & 6 & & 1\\ 10 & & 4 \\ & 10 & & 1\\ 20 & & 5\\ & 15 & & 1\\ 35 & & 6 \\ & 21 & & 1\\ 56 & & 7\\ & 28 \\ 84 \\ \end{array}

$1$-st column: given numbers.
$2$-nd column: differences: $3 = 4-1, \ \ 6 = 10-4, \ \ 10 = 20 - 10, \ \ldots$.
$3$-rd column: differences: $3 = 6-3, \ \ 4 = 10-6, \ \ 5 = 15-10, \ \ldots$.
$4$-th column is constant column, so it must be formula

$$ a_n = c_0 + c_1 n + c_2 n^2 + c_3 n^3. $$

To find next value, we'll continue table:

\begin{array}{|c|c|c|c|} 1 &\\ & 3 &\\ 4 & & 3\\ & 6 & & 1\\ 10 & & 4 \\ & 10 & & 1\\ 20 & & 5\\ & 15 & & 1\\ 35 & & 6 \\ & 21 & & 1\\ 56 & & 7\\ & 28 & & \color{red}{1}\\ 84 & & \color{red}{8}\\ & \color{red}{36}\\ \color{red}{120} \\ \end{array}

$\color{red}{1}$ $-$ because $4$-th column is constant;
$\color{red}{8} = 7+\color{red}{1}$;
$\color{red}{36} = 28+\color{red}{8}$;
$\color{red}{120} = 84+\color{red}{36}$;

If you want to find out formula, then you can create system:

$$ \left\{ \begin{array}{r} c_0 + c_1+c_2+c_3 = 1; \\ c_0 + 2 c_1+4c_2+8c_3 = 4; \\ c_0 + 3 c_1+9c_2+27c_3 = 10; \\ c_0 + 4 c_1+16c_2+64c_3 = 20. \\ \end{array} \right. $$

System with Vandermonde matrix.

$$ \left\{ \begin{array}{r} c_0 + c_1+c_2+c_3 = 1; \\ c_1+3c_2+7c_3 = 3; \\ 2 c_1+8c_2+26c_3 = 9; \\ 3 c_1+15c_2+63c_3 = 19. \\ \end{array} \right. $$

$$ \left\{ \begin{array}{r} c_0 + c_1+c_2+c_3 = 1; \\ c_1+3c_2+7c_3 = 3; \\ 2c_2+12c_3 = 3; \\ 6c_2+42c_3 = 10. \\ \end{array} \right. $$

$$ \left\{ \begin{array}{r} c_0 + c_1+c_2+c_3 = 1; \\ c_1+3c_2+7c_3 = 3; \\ 2c_2+12c_3 = 3; \\ 6c_3 = 1. \\ \end{array} \right. $$

Then we get:

$$ \left\{ \begin{array}{l} c_3 = \dfrac{1}{6}; \\ c_2= \dfrac{1}{2}; \\ c_1 = \dfrac{1}{3}; \\ c_0 = 0. \\ \end{array} \right. $$

So,

$$a_n = \dfrac{n}{3} + \dfrac{n^2}{2}+\dfrac{n^3}{6} = \dfrac{2n+3n^2+n^3}{6}.$$

You can test this formula:

$a_1 = \dfrac{2+3+1}{6}=1$,

$a_2 = \dfrac{4+12+8}{6}=4$,

$a_3 = \dfrac{6+27+27}{6}=10$,

$\ldots \ldots$.

Oleg567
  • 17,295
  • I'm sorry but I'm quickly realising I'm even worse at mathematics than I thought. Could you substitute some numbers there so I can understand how it's pulled together? Sorry for my naivety.. – Ant Jun 27 '13 at 22:42
  • I just edited answer. Do you understand now how to derive next number of the sequence? – Oleg567 Jun 27 '13 at 22:53
  • I almost understand it. I'm sorry; I've been away from anything more advanced than simple addition for a few years now. This is probably the most obvious thing, but what do the subscript numbers mean? – Ant Jun 27 '13 at 23:03
  • red numbers - are continuation of table ... – Oleg567 Jun 27 '13 at 23:09
  • numbers in $c_0,c_1,c_2,c_3$ $-$ just indices, just marks. $c$ $0$-th, $c$-first, $c$-second, $c$-third. Four different variables. – Oleg567 Jun 27 '13 at 23:18
  • With the Vandermonde matrix. section I can see that the first you're taking 1 away from everything so $2c_1$ becomes $c_1$ and $4c_2$ becomes $3c_2$, but with the second step how does $8c_2$ become $2c_2$? – Ant Jun 27 '13 at 23:32
  • Here I substitute $2\times$ Row2 of Row3: $(2c_1+8c_2+26c_3) - 2\cdot(c_1+3c_2+7c_3) = 2c_2+12c_3$. Right side $-$ same way: $9 - 2\cdot 3=3$. – Oleg567 Jun 27 '13 at 23:42
  • Thank you so much @Oleg567 you have been an immense help! I feel like I've been on a bit of a journey. But I think I've got there. Thank you very much =]

    I think maybe the title of this post could have an edit to help people find this information a little easier. Not sure what I'd call it though...

     – Ant Jun 27 '13 at 23:45
  • You're welcome, @Ant. – Oleg567 Jun 27 '13 at 23:46
2

try again. Last night it would not let me post the jpeg of Pascal's triangle from my home computer.

Good, that worked. The "diagonals" are the strings of numbers parallel to the boundary strings of all 1's. Your $1,4,10,20,35,56,84,\ldots$ is the fourth diagonal. It is symmetric, so parallel to either edge of 1's.

enter image description here

Will Jagy
  • 139,541
1

In general, it helps to know some other standard sequences when you're looking at first differences. In fact, the sequence that you have listed has a known name. (Don't mouse over if you don't want to see...)

Tetrahedral Numbers

apnorton
  • 17,706
0

Just to answer the question actually posted in the title: Yes, it is possible to have number sequences that have no closed form or formula to generate them, especially integer sequences. The output of a recurrence relation is a number sequence, and the general class of recurrence relations is Turing-complete, so there will be number sequences which cannot even be shown to continue or terminate, hence cannot in general be calculated except by some recurrence relation.

Exapno Mapcase
  • 1