# Find the $n^{th}$ term for this sequence

I have the following sequence:

4, 7, 11, 19, 36, 69

Now, I've done the usual and found the differences, and it goes down to four levels until I get a common difference, suggesting I have to use $n^{4}$ somewhere, but I just can't find the nth term. Any help? And if you know of any easier methods to finding the nth term, I'd appreciate it.

P.S. - I know about the formulas for arithmetic progression and geometric progression, but clearly neither can be used here.

-
Well, you are presuming your data was generated by $p(x)=ax^4+bx^3+cx^2+dx+f$. Replace $x$ with the index and $p(x)$ with the corresponding number, e.g. $4=a\times 1^4+b\times 1^3+c\times 1^2+d\times 1+f$ for the first one. You'll end up with five equations in the five unknowns, where you can take any five of the six... – J. M. Sep 30 '11 at 16:35
The problem is that there are uncountably many sequences that start with 4,7,11,19,36,69... – user5137 Sep 30 '11 at 17:11

The first numbers in each row of differences are 4, 3, 1, 3, 2. Assuming that the last row is all 2's then the formula is $$4\binom n0+ 3\binom n1 + 1\binom n2 + 3\binom n3 + 2\binom n4$$ starting at $n=0$. This is an instance of the Newton series.

The formula simplifies to $$\frac{n^4 - n^2 + 36 n + 48}{12}$$ but this is not enlightening.

-
As I said before, I'm just in the 10th grade (so no calculus), so I didn't really understand that, but the formula works, so clearly your answer is correct. Hopefully I'll understand this as I learn. – Some Guy Sep 30 '11 at 16:53
@Amaan, if you don't know the notation $\binom n k$, it's the binomial coefficient, which you'll probably learn soon. – lhf Sep 30 '11 at 16:56
Yeah, that's what confused me. Okay, thanks. – Some Guy Sep 30 '11 at 16:58

There are infinitely many sequences which start with that initial segment. Since there are five terms, there will definitely be a 4th degree equation which fits it, but unless the problem is to find the simplest polynomial equation which generates that sequence, it's not clear that a polynomial would be the correct way to go (unless the minimal degree polynomial fitting the data is of lower degree than expected).

If we eyeball the sequence, we see that each term is approximately doubling each time. This suggests that the sequence is of the form $a2^n+f(n)$ for some small $f(n)$.

For example, if we subtract off $2^n+n$ from the $n$th term, we get the new sequence:

$$1,1,0,-1,-1,-1\ldots$$

If we define the sign function $\sigma(n)=\frac{|n|}{n}$ if $n\neq 0$ and $\sigma(0)=0$, we can thus write the sequence as $$2^n+n+\sigma(3-n).$$
Is this the "right" answer? I honestly can't say. Without more terms, there are probably quite a lot of relatively simple answers which will fit the sequence. Having more terms (or knowledge of what kind of answer they are looking for) would help eliminate some of these possibilities.

-
Well, those were all the terms that had been given, and there really wasn't a question, because the question asked for the next two terms, which shouldn't be too hard to find because the second differences sequence is clearly just square numbers. I just wanted to try finding the nth term. – Some Guy Sep 30 '11 at 17:24
@Amaan Finding the next term is in some sense equivalent to finding the nth term. Any finite sequence is part of infinitely many different infinite sequences, and the question is "what is the simplest pattern the initial segment satisfies, and what are the next terms of that pattern." You cannot say "the next two terms are ____" unless you claim to know the pattern which generates all the terms. Any single element can continued to a constant sequence, any two can be continued to an arithmetic progression, any 5 satisfy some 4th degree polynomial. (continued) – Aaron Sep 30 '11 at 17:47
The fact that the six terms here satisfy a 4th degree polynomial and not just a 5th degree one means that you have found structure. The question is, might there be simpler structure which generates the same initial segment? What would simpler mean? If we satisfied a third degree polynomial, I would definitely say we found the pattern, because we have two extra datapoints to confirm that we're on the right path. For a 4th degree, we only have one extra data point, which feels too much like coincidence. (continued) – Aaron Sep 30 '11 at 17:54
I guess the point I want to make is that generalizing from a small amount of data is a very dangerous game. For example, a sequence starting $(1,0,1,\ldots)$ could be a fibonacci type sequence, alternating $0$ and $1$, quadratic ($f(n)=(n-1)^2$), many more, some of which are simple and some of which are horrendously complicated. There is no right answer, and you honestly can't even say what the next element is without implicitly saying what the general pattern is. – Aaron Sep 30 '11 at 18:05