Baffled by resolving number list

Question

My son's Maths homework was to do with number patterns/sequences. "What is the nth term?". He'd done very well, but the last sequence was something like this:

19,77,265,715,1607,3169

He was adamant that he didn't have a technique for solving it and that it must be a "fake" question. However, something about the numbers looked like there could be a pattern so I did a bit of investigating.

I put them into a spreadsheet and found the differences between consecutive numbers:

58, 188, 450, 892, 1562

No clues. I decided to find the differences of this list:

130, 262, 442, 670

They appear to be getting less diverse with each step:

132, 180, 228

Then:

48, 48

I found that I could generate a list like this using a formula:

$$\begin{align}ax^n+bx^p+cx^q+dx+y\end{align}$$

I can have as many power terms as I like but difference always resolves after a number of steps equal to the highest power.

Can anyone explain what's happening here please? I am not a Mathematician, so please keep it as simple as possible.

Answer 1

What you are computing is a binomial transform (see on Wikipedia or MathWorld)

If your original sequence is $u_0,\dots,u_n$, you compute successive differences of your list, and you keep only the first term of these differences.

The differences are

$$\begin{matrix} 19 & 77 & 265 & 715 & 1607 & 3169\\ 58 & 188 & 450 & 892 & 1562\\ 130 & 262 & 442 & 670\\ 132 & 180 & 228\\ 48 & 48\\ 0 \end{matrix}$$

So the list of first terms is $(v_k)=(19,58,130,132,48)$, with last nonzero term being here $v_4=48$, and you can then write, with $m=4$,

$$u_n=\sum_{k=0}^{m} {n \choose k}v_k$$

That is

$$u_n=19{n \choose 0}+58{n \choose 1}+130{n \choose 2}+132{n \choose 3}+48{n \choose 4}\\ =2n^4+10n^3+21n^2+25n+19$$

And by this method, your next term is $u_6=5677$.

Now, the reason why this works is that, given a sequence $u_n$, if you define, for all $n\geq0$,

$$v_n=(-1)^n\sum_{k=0}^n (-1)^k{n \choose k}u_k$$

Then you have, for all $n\geq0$,

$$u_n=\sum_{k=0}^n {n \choose k}v_k$$

I won't give a proof since you want to keep things simple, but at least you can see where the first sum comes from. If you compute the first term of successive differences of $u_n$, you have:

$$u_0$$ $$u_1-u_0$$ $$(u_2-u_1)-(u_1-u_0)=u_2-2u1+u_0$$ $$(u_3-2u_2+u_1)-(u_2-2u_1+u_0)=u_3-3u_2+3u_1-u_0$$ $$(u_4-3u_3+3u_2-u_1)-(u_3-3u_2+3u_1-u_0)=u_4-4u_3+6u_2-4u_1+u_0$$

And you should see a pattern.

Also, since

$${n \choose k}=\frac{n(n-1)\cdots(n-k+1)}{k!}$$

You can thus write your second sum as a polynomial in $n$.

---

An interesting feature of binomial transform is that if you original sequence is a polynomial of degree $m$, then the successive differences vanish after the $m$th, and you recover your polynomial in terms of binomial coefficients (it's just a change of basis).

Another way to view this is, if you have a finite sequence (of length $m$), you can compute all possible differences, that is up to the $(m-1)$th, and assuming all the following differences would be zero, you reconstruct the interpolating polynomial $P$ (then of degree $m-1$), such that $P(0)$ is you first term, $P(1)$ the second, etc. It's a practical way to compute the interpolating polynomial when absissas are the integers $0,1,\dots m-1$. Notice that it's a special case of Newton interpolation.

I wrote that with a list of length $m$ you get a polynomial of degree $m-1$, actually it's of degree at most $m-1$. You may have noticed that in your case, the last difference is zero, so the polynomial has degree $m-2=4$.

---

Seeing such a question, you may actually answer any number you wish for the next one, as you can always (at least) find an interpolating polynomial that would give this number. For example, you just have to add it to your list, and compute the binomial transform with the expanded list, to recover a new polynomial. Of course, it's not what is expected, but such an exercise is not very interesting, from the mathematical viewpoint.

However, it happens in practice that you have a sequence that you want to identify, and the binomial transform may be extremely useful to find a pattern, though it does not work in all cases. And another very useful tool is OEIS. It's just a database, but it's a huge one.

Answer 2

Suppose we have given any "pattern" of $n$ numbers

$$c_1,c_2,\cdots,c_n$$

So in your example $n=6$ and $c_1=19, c_2=77, \cdots$.

Then what you basically discovered is the fact that we can always find a "rule" in the form of a polynomial of degree at most $n-1$,

$$P(x)=a_{n-1}x^{n-1}+\cdots+a_1 x+a_0$$

such that $P(1)=c_1, P(2)=c_2, \dots, P(n)=c_n$.

The reasons this works is simple: We are searching the $n$ coefficients $a_{n-1},\dots a_0$ such that the $n$ equations $P(k)=c_k$ for $k=1,\dots,n$ are true. That is we are solving a system of $n$ linear equations:

$$\left\{\begin{array}{ll} a_{n-1} 1^{n-1} +& \cdots +& a_1 1^1 +& a_0 1^0 &= c_1\\ a_{n-1} 2^{n-1} +& \cdots +& a_1 2^1 +& a_0 2^0 &= c_2\\ a_{n-1} 3^{n-1} +& \cdots +& a_1 3^1 +& a_0 3^0 &= c_3\\ \vdots & \cdots & \vdots & \vdots & \vdots\\ a_{n-1} n^{n-1} +& \cdots +& a_1 n^1 +& a_0 n^0 &= c_n\\ \end{array}\right.$$

So we have $n$ equations and $n$ unknowns. From school you may remember that in such a situation you can generally expect to find a solution for your unknowns (unless the equations contain "contradictions").

The mathematically precise reason why the solution can be found here is that the coefficient matrix (which coincidentally has a name and is referred to as Vandermonde matrix) is invertible. Therefore there exists a uniquely determined polynomial of degree smaller-equal $n-1$ giving the "rule" for the given "pattern".

The difference scheme that you gave is a way of solving this particular system of equations.

Answer 3

FYI, you can easily find a polynomial equation that fits that sequence in Excel. This is probably not what the teacher is looking for, but it's really easy.

1. Paste those numbers into a column in Excel.

2. Highlight the cells and insert a scatter plot

3. Right-click on a point and click "Add Trendline..."

4. Check the "Display Equation" and "Display R-squared" checkboxes.

5. Click on the regression types and play with then inputs until your R-squared equals 1.

I got an equation by setting the trend type to Polynomial and the order to 4. The equation is:

y = 2x^4 + 2x^3 + 3x^2 + 5x + 7

The next value is 5677 which agrees with your guess. This does feel like cheating though.

Answer 4

Suppose we have some sequence generated by evaluating a polynomial $$P(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots+ a_1 x+a_0$$ at integers $x=0,1,2,3,$ etc. What can we expect about its sequence of consecutive differences? If we take the difference between the $x$-th term and the $(x+1)$-th term, and organize by coefficients, we have

$$P(x+1)-P(x)=a_n((x+1)^n-x^n)+a_{n-1}((x+1)^{n-1}-x^{n-1})+\cdots+a_0((x+1)-x)$$ This is a rather complicated expression, but there's a key observation. Suppose we perform the (tedious) multiplication involved in expanding an expression like $(x+1)^n-x^n$: then the term $x^n$ will be cancelled out, and we'll be left with some (complicated) polynomial of the form $$P'(x)=a'_{n-1}x^{n-1}+a'_{n-2}x^{n-2}+\cdots +a'_1 x+a_0'.$$

The implication we can draw is that, if we start with a sequence generated by a polynomial with leading term $x^n$, then taking differences gives us a new sequence generated by a polynomial with leading term $x^{n-1}$. This is great since we can repeat this: If we repeat this process a total of $n$ times, we'll end up with a sequence that is constant (maybe with the leading term being different than the rest.)

To apply this to your problem, note that we had to carry out four 'differences' of your son's sequence to reach a constant. Therefore the sequence is generated by some polynomial $P(x)=a x^4+b x^3+c x^2+d x+f$ as you concluded.

Answer 5

I'd post this as a comment but don't have the reputation to allow it ...

Lefty, you commented that you thought you'd find this sort of technique useful in practical ways ... well, ok, but ...

Beware that using this method, the next number can be anything you want ! i.e. pick any value at all as the 7th term in the series, and you'll be able to derive a polynomial that matches it and the first 6 numbers too, this time using a polynomial that goes up to something times x^6.

Unfortunately, in practical problems, using long polynomials to match real data is almost always a bad move, unless you have some clue that the underlying process really does follow a particular long polynomial. It's a method that will seem to work beautifully for a while, but then fall to pieces completely when you least expect it.