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.
Best Answer
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.