14
$\begingroup$

I was thinking about what happens if you take a sequence of consecutive squares, for example 1,4,9, 16. Taking the differences gives you another sequence, 7,5,3. And taking the differences between those numbers, you get 2,2--a constant. Through elementary first-semester algebra, you can easily verify that this works no matter where you start your series of squares. If you use 9801, 10000, 10201, you will get the same result--after the second round of subtraction, you'll end up with a final constant difference of 2. The same thing works for cubes with the final constant difference being 6, although an additional round of subtraction is needed, in turn requiring one more number in the original sequence. Similarly as with the squares, it's not difficult to show that it will work for any sequence of natural number cubes.

My question is this: Is there a more general principle at work here? Suppose I take a series of sequential naturals n, n+1, n+2, n+3,... , and raise them to any given positive integral power p. Can it then be shown that if I take the differences repeatedly, proceeding as above, that I will eventually reach a constant difference? And if so, does this principle have anything to do with "difference engine" computing?

$\endgroup$
3
  • $\begingroup$ Side note: The eventual constant difference is $p!$, where $p$ is the power. $\endgroup$
    – Brian Tung
    Jun 30 '15 at 23:40
  • 2
    $\begingroup$ You should take a look at Faulhaber's formula. (Note that taking differences of the numbers $$S_p(n),\;\;S_p(n+1),\;\;\ldots,\;\;S_p(n+k),\;\;\ldots$$ produces the sequence $$n^p,\;\;(n+1)^p,\;\;\ldots,\;\;(n+k)^p,\;\;\ldots$$ and then you can continue taking differences from there.) $\endgroup$ Jun 30 '15 at 23:41
  • $\begingroup$ Thanks for the answers and comments so far. And yes, a proof will definitely be in the works...not because the world needs it, but because I need to see it work for myself, as I did for the special cases ^2 and ^3. I do wish that when I was in school they had emphasized proofs instead of what seemed to me, at the time, merely a random grab-bag of disconnected rules and tricks. $\endgroup$ Jun 30 '15 at 23:46
18
$\begingroup$

Yes.

The first difference of a polynomial of degree $d$ is a polynomial of degree $d-1$.

By induction, the $m$-th difference of a polynomial of degree $d$, when $m \le d$, is a polynomial of degree $d-m$.

Setting $m = d$, the $d-th$ difference of a polynomial of degree $d$ is a constant, which is exactly what you discovered.

You next step is a proof.

$\endgroup$
9
$\begingroup$

If you start with the sequence of $n$-th powers, the $n$-th differences will all be $n!$.

For a function $f$ defined on the integers define $(\Delta f)(x)=f(x+1)-f(x)$. $\Delta$ is a linear operator on such functions: you can easily check that $\Delta\big(af(x)+bg(x)\big)=a\Delta f(x)+b\Delta g(x)$ for any such functions $f$ and $g$ and constants $a$ and $b$.

Now suppose that $\Delta^k(x^k)$ is the constant function $k!$ for each $k<n$. For any constant function $f$ the difference function $\Delta f$ is identically $0$, so $\Delta\big((\Delta^k(x^k)\big)=\Delta(k!)=0$ for each $k<n$, and it follows that $\Delta^m(x^k)=0$ whenever $k<n$ and $m>k$. In particular, $\Delta^{n-1}(x^k)=0$ for $k<n-1$. Thus,

$$\begin{align*} \Delta^n(x^n)&=\Delta^{n-1}\big((x+1)^n-x^n\big)\\ &=\Delta^{n-1}\left(\sum_{k=0}^n\binom{n}kx^k-x^n\right)\\ &=\Delta^{n-1}\left(\sum_{k=0}^{n-1}\binom{n}kx^k\right)\\ &=\sum_{k=0}^{n-1}\binom{n}k\Delta^{n-1}(x^k)\\ &=\binom{n}{n-1}\Delta^{n-1}(x^{n-1})\\ &=n(n-1)!\\ &=n!\;, \end{align*}$$

and by induction $\Delta^n(x^n)=n!$ for all $n$. (You can easily check the basis step of the induction.)

These so-called forward differences are a special case of divided differences, after which Babbage’s Difference Engine was named.

$\endgroup$
3
$\begingroup$

Using the Binomial Theorem, we get $$ (n+1)^k-n^k=\sum_{j=0}^{k-1}\binom{k}{j}n^j $$ So the difference of two consecutive $k^\text{th}$ powers is a $k-1$ degree polynomial with lead coefficient $\binom{k}{k-1}=k$. Thus, the difference of a degree $k$ polynomial with lead coefficient $c_k$ is a degree $k-1$ polynomial with a lead coefficient of $kc_k$.

Repeating this, we get that the $k^\text{th}$ repeated difference of $k^\text{th}$ powers (a degree $k$ polynomial with lead coefficient $1$) will be $k!$.

$\endgroup$

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.