20
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Note that if you take differences of $x^n$ you get $(x+1)^n-x^n$ which is a polynomial of degree one less, that is, degree $n-1$ (because when you subtract the $x^n$-terms cancel). So if you do it $n$ times you get a polynomial of degree zero, which is to say, you get a constant. $\endgroup$ – Gerry Myerson Sep 17 '14 at 13:24
  • 1
    $\begingroup$ If you have, say, four random numbers $a,b,c,d$ you can always find a polynomial (that is a function like $f(x)=k_0+k_1x+k_2x^2+...+k_nx^n$) of degree $3$ that passes through them. Same goes for any list of numbers; if you have $n$ numbers you can find a polynomial of degree $n-1$ which suits the case. $\endgroup$ – marco trevi Sep 17 '14 at 13:25
  • $\begingroup$ I'm sure these comments and the 1 Answer so far have answered the question - but they're all beyond my knowledge of Maths unfortunately. I'll have to spend some time to understand what this all means before I can comment. $\endgroup$ – Lefty Sep 17 '14 at 13:39
  • 1
    $\begingroup$ Calculation of such sequences was actually deemed important enough to warrant the invention of one of the earliest forerunners of modern computers. I am surprised that nobody has so far commented on Babbage's difference engine, whose original purpose was to construct such sequences: en.wikipedia.org/wiki/Difference_engine $\endgroup$ – Boluc Papuccuoglu Sep 17 '14 at 16:04
  • 3
    $\begingroup$ It doesn't really help your son but these are terrible questions (one could even say "fake") because one can assert that any number is the next in the sequence. For example, I claim that the answer is 48765 because the sequence is the set of solutions to the equation $(x-19)(x-77)(x-265)(x-715)(x-1607)(x-3169)(x-48765)=0$. $\endgroup$ – David Richerby Sep 17 '14 at 19:01
10
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ "You may have noticed that in your case, the last difference is zero, so the polynomial has degree m−2=4." -- and if that were not the case, then personally I would look for a different rule to define and extend the sequence. For example, given "2, 4, 8, 16" and asked for the next term, it's pretty certain that the "correct" answer is not to extrapolate a cubic! Unfortunately "next term in the sequence" questions pretty much always admit more than one answer that's at least semi-plausible, so it's possible to miss the one you were supposed to find but think you've answered the question. $\endgroup$ – Steve Jessop Sep 17 '14 at 19:02
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for the answer but this is WAY beyond my Maths level - the same goes for all the other answers here. As they say in all the RomComs, "It's not you, it's me." I'm just not great with these abstract concepts and have to always work with examples, playing with the numbers until some general concept falls out in the right shape to fit in my head. $\endgroup$ – Lefty Sep 18 '14 at 22:33
  • $\begingroup$ Am I right in saying that the fact that I created this list using an equation is NOT the reason you can resolve the list to an equation using this procedure? If I were to present you with 23, 1002, 1003, 1019, 57367 and 58444 you would still be able to derive an equation the fits them all? That sounds remarkable to me if it's true. $\endgroup$ – Lefty Sep 18 '14 at 22:40
  • $\begingroup$ Yes, this is exactly the point. @Lefty No matter what totally random numbers you throw me (say 1000 of them), I can give you a polynomial of degree at most 999 that generates them. $\endgroup$ – J.R. Sep 19 '14 at 7:29
  • 2
    $\begingroup$ I find that incredible. You might be happy to hear that I am beginning to understand this a bit now, mainly thanks to being able to use the Excel cheat suggested by user2023861 below. I managed to find a polynomial that fits the 6 numbers in my comment above - totally amazed by that! It's mainly the jargon that separates me from these concepts, but I'm fighting through it. $\endgroup$ – Lefty Sep 19 '14 at 19:33
  • $\begingroup$ I am happy to hear that! :) @Lefty $\endgroup$ – J.R. Sep 19 '14 at 19:43
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I tried this today with the list I suggested in one of my comments above. It WORKED! Absolutely brilliant, thank you very much for enlightening me on this valuable function in Excel. I use Excel a great deal in my job but don't often get involved in anything to do with graphs so never knew this function existed. It will prove very useful to me in practical ways I am sure. $\endgroup$ – Lefty Sep 19 '14 at 18:32
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks @user156408. I'd picked-up the idea you mention from earlier answers. For my purpose I think the general feature of Excel will be useful simply for the interpolation aspect. I'm an analyst/developer and quite frequently have lists of examples that I have to use to establish a general principle within a program. I can usually establish the rule OK manually - but this will help with that process. $\endgroup$ – Lefty Sep 21 '14 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.