Copyright © University of Cambridge. All rights reserved.
Before you read this article you are advised to try the
Difference Dynamics
investigation. Start with a finite sequence, for example (25,
42, 6). The differences between your numbers give you three
new numbers (17, 36, 19). Repeat this operation to give a sequence
of sequences. In this example the sequence of sequences continues:
(19, 17, 2), (2, 15, 17), (13, 2, 15), (11, 13,
2), (2, 11, 9) , (9, 2, 7), (7, 5, 2), (2, 3,
5), (1, 2, 3), (1, 1, 2), (0,1,1) etc. You can
produce chains of sequences like this for sequences of any length.
The rule for generating these sequences is that you take the moduli
of the differences between adjacent terms, taking the difference
between the last term and the first term, to get the next
sequence in the chain and repeat this process to get a sequence of
sequences.
Read no further. You can try this for yourself, starting with a
sequence of any length. Carry out your own investigation, make some
conjectures about the behaviour of the sequences that you observe,
at least for sequences of two, three and four terms, and try to
prove your conjectures. When you tire of your own thoughts and you
want to know what others have done with these ideas then read
on.
This investigation is well known and has a long history. The
problem is attributed to the Italian Enrico Ducci in the late
1800's, and the first proof of the theorem that is proved in this
article seems to have appeared in 1937. The usual proof involves,
among other things, expanding a sum of matrices by the binomial
theorem over the field $\mathbb{Z}_2$. However, as the problem can
be tackled by school students, it seems desirable to have
elementary proofs of the conjectures they might make. The purpose
of this article is to provide such proofs.
A little experimentation leads to sequences that repeat in a
cyclic pattern or to the
sequence of sequences stopping with the zero sequence $(0, 0,
...0)$ which we call a
fixed
point of this iteration. This behaviour is typical of
dynamical systems which are very important in mathematics.
There are many situations in which we want to measure
something that changes with time, either discretely (say every
week) or continuously. For example, we may count the number of
elephants in Africa each year or record the temperature
continuously at some spot in London. A dynamical system is a
mathematical model of such a system, and dynamical systems are
often used to predict population growth, weather, and so
on. The essential feature of this type of system is that there
is a set of all the possibilities for the measurements,
together with some mathematical rule which tells us how our
measurement will change with time. An important feature in any such
model are the fixed points in the model: if the measurement is
$X_n$ and the rule is $X_{n+1}=f(X_n)$ for some function
$f$, then a fixed point is a measurement $X$ such that $f(X) =
X$. In this case, if some $X_n$ takes the value $X$ then
$X_{n+1}=X_n=X$ and the population (for example) will remain at
this fixed value for ever. A more general situation is when
the sequence of measurements oscillates like for example,
$A,B,A,B,A,...$ or $A,B,C,A,B,C,A,...$ giving
cycles of periods two and three.
Measurements in nature are often seen to follow cyclic
patterns.
In this Difference Dynamics investigation, many sequences converge
to repeating cycles such as$ (k, k, 0), (0, k, k), (k, 0, k), (k,
k, 0)$ and some sequences end with the zero sequence $(0, 0, 0,
... 0)$ making it a fixed point for this iteration. So which
sequences of sequences end with the zero sequence? Do all other
sequences end in cycles?
As a first step let us prove that if this process does not produce
a sequence of zeros then it must lead to a repeating cyclic
pattern. Notice that after the first sequence all the numbers in
the sequences are positive so without loss of generality we'll
consider sequences with positive terms. Then taking differences in
this iterative process makes sure that the largest number in the
sequence stays the same or gets smaller.
The proof depends on the same reasoning as you can use to prove
that if your school is big enough then there are at least two
people in the school who have the same birthday. As there are only
366 possible birthdays, if there are more than 366 people in your
school then at least two people must share a birthday.
The sequence we used as an example started with (25, 42, 6) so no
number in any of the subsequent sequences can be bigger than 42. It
follows that there are at most 43 choices (0 to 42) for each
number in the sequences making at most $43^3$ different
possible sequences. There are not an infinite number of
possibilities, so just as with the birthday example, sooner or
later the iteration must repeat a sequence that has
appeared earlier and repeat the earlier pattern. The same argument
applies for any finite starting sequence of any length and so we
have proved that these sequences always end in the zero sequence or
in cycles.
You will no doubt have noticed that all sequences of length 2 and 4
seem to end with the zero sequence and all non-constant sequences
of length 3 end in cycles and you may have conjectured that there
is a significant difference for sequences of odd and even length.
This is not so as you will have discovered if you tried sequences
of length 6. If you pursued the investigation far enough you
may have noticed the result in the theorem below for which we
give a proof that uses nothing more than school mathematics.
Let $(a_1,\ldots,a_n)$ be a sequence of integers, and let
$\theta$ be the operation $$\theta: (a_1,\ldots,a_n) \mapsto
(|a_1-a_2|,\ldots,|a_{n-1}-a_n|, |a_n-a_1|).$$ Throughout we write
$\mathbf{a} = (a_1,\ldots,a_n)$, and so on, and
$\mathbf{0}=(0,\ldots,0)$. Clearly, we need only consider
sequences with non-negative elements (since this will be so
after just one application of $\theta$), so all sequences in
this discussion will be assumed to have non-negative integral
elements. For a positive integer $q$, $\theta^q$ denotes the $q$-th
iterate of $\theta$.
First, suppose that $\theta(\mathbf{a}) =\mathbf{b}$. We show that
$\mathbf{a}$ is a constant sequence if and only
if $\mathbf{b}$ is the zero sequence. Clearly if
$\mathbf{a}$ is a constant sequence then $\mathbf{b}$ is
the zero sequence. Now suppose that $\mathbf{b}$ is the zero
sequence so we have $|a_j - a_{j+1}|= b_j = 0$ for all $j$.
Thus $a_1 = a_2 = ... = a_n$ so that $\mathbf{a}$ is a
constant sequence. Can $\mathbf{b}$ be a constant
sequence without being the zero sequence? Now if $n$ is even
and $\theta(\mathbf{a}) =\mathbf{b}$ it is possible
for $\mathbf{b}$ to be a constant non-zero sequence, for
example if $\mathbf{a} =(1,2)$ then $\mathbf{b}=
(1,1)$. However if $n$ is odd, this is not possible as we
show below.
Theorem Every sequence
$(a_1,\ldots,a_n)$ eventually maps to $(0,\ldots,0)$ under repeated
applications of $\theta$ if and only if $n=1, 2, 4, 8, 16 ... $,
that is $n=2^m$ for some integer $m$.
We divide our proof into three cases: (i) $n$ is odd, (ii) $n$ has
an odd factor, and (iii) $n=2^m$ for some $m$.
Section (i) $n$ is
odd
We suppose that $n$ is odd. Suppose $\theta(\mathbf{a})$ is
constant
, say
$(b,b,\ldots,b)$. Then, for $j=1,\ldots,n$, we have
$|a_j-a_{j+1}|=b$ (where we put $a_{n+1}=a_1$). Thus we can write
$a_j-a_{j+1} = \varepsilon_jb$, where $\varepsilon_j = \pm 1$, and
$b(\varepsilon_1+\cdots +\varepsilon_n)=0$. Since the sum of the
$\varepsilon_j$ cannot be zero (because $n$ is odd), we see that
$b=0$. Thus $\theta(\mathbf{a})=\mathbf{0}$. Hence, from above,
$\mathbf{a}$ is constant. These facts show that only constant
sequences map to constant sequences under $\theta$ or,
equivalently, that non-constant sequences map to non-constant
sequences. Thus if $n$ is odd, and if we start with a sequence that
is not constant, then it will never reach $\mathbf{0}$.
Section (ii) $n$ has an odd
factor
We shall give the argument for $n=6$ (which has $3$ as an odd
factor), and this clearly generalises to any $n$ with an odd
factor. We know from Section (i) for any non-constant sequence
$(a_1,a_2,a_3)$ we have $\theta^p(a_1,a_2,a_3) \neq (0,0,0)$ for
any integer $p$. Now if $\theta^p(a_1,a_2,a_3) = (b_1,b_2,b_3)$,
then $$\theta^p(a_1,a_2,a_3,a_1,a_2,a_3) =
(b_1,b_2,b_3,b_1,b_2,b_3),$$ and it follows from this that
$\theta^p(a_1,a_2,a_3,a_1,a_2,a_3) \neq (0,0,0,0,0,0)$ for any $p$.
In general, if $n$ has an odd factor then there is a
sequence $\mathbf{a}$ which will never reach $\mathbf{0}$. We
have now shown that if all sequences eventually reach $\mathbf{0}$,
then $n$ cannot have an odd factor, so that $n=2^m$ for some $m$.
Section (iii) $n$ is a power of
$2$
We now assume that $n=2^m$. Our proof uses the following
lemma.
Lemma For any starting
sequence $\mathbf{a}$, $\theta^n(\mathbf{a})$ has even
components.
Let us assume this lemma for the moment, and show how it enables us
to complete the proof of the theorem. Take any $\mathbf{a}$ and
choose an integer $p$ such that each component of $\mathbf{a}$
is strictly less than
$2^p$. Now, by our Lemma, we can write $\theta^n(\mathbf{a}) =
2\mathbf{a}_1$, where $\mathbf{a}_1$ is some sequence. In the same
way, we can write $\theta^n(\mathbf{a_1}) = 2\mathbf{a}_2$, and so
on, until we reach $\theta^n(\mathbf{a}_{p-1}) = 2\mathbf{a}_p$. It
is now clear that $ \theta^{np}(\mathbf{a}) = 2^p\mathbf{a}_p.
$ Now, for any $\mathbf{x}$, the maximum component of
$\theta(\mathbf{x})$ is at most the maximum component of
$\mathbf{x}$. Because the maximum component of
$\theta^{np}(\mathbf{a})$ is strictly less than $2^p$, we must have
$\mathbf{a}^p = \mathbf{0}$; thus $\theta^{np}(\mathbf{a})
=\mathbf{0}$ and so if the lemma holds we have proved the
theorem.
It remains to prove the lemma and we do this by considering a
function $\rho$ that is closely related to $\theta$. The function
$\rho$ acts on
infinite
sequences of non-negative integers as follows:
$$\rho(a_1,a_2,a_3,\ldots) = (|a_1-a_2|,|a_2-a_3|,
|a_3-a_4|,\ldots).$$
Notice that the action of $\theta$ on sequences of length $n$ can
be obtained from $\rho$ by taking the sequence $(a_1,a_2,\ldots)$
to be periodic of period $n$ so this proof works for all values of
$n$. Now $$\rho^2(a_1,a_2,a_3,\ldots) =
(\big||a_1-a_2|-|a_2-a_3|\big|,\ldots).$$ The key observation now
is that if $q$ is an integer then $q$ and $|q|$ have the same
parity (both odd or both even). Thus
$\big||a_1-a_2|-|a_2-a_3|\big|$ has the same parity as
$a_1-2a_2+a_3$, which has the same parity as $a_1+a_3$. If we now
use the notation $(a_1,a_2,\ldots)\sim (b_1,b_2,\ldots)$ to mean
that $a_j$ and $b_j$ have the same parity for all $j$, then we see
that $$\rho^2(a_1,a_2,a_3,\ldots) \sim
(a_1+a_3,a_2+a_4,a_3+a_5,\ldots).$$ If we now apply $\rho^2$ to the
sequence on the right we find that $$\rho^4(a_1,a_2,a_3,\ldots)
\sim (a_1+a_5,a_2+a_6,a_3+a_7,a_4+a_8,a_5+a_9,\ldots).$$ Next, we
apply $\rho^4$ to the sequence on the right: this gives
$$\rho^8(a_1,a_2,a_3,\ldots) \sim (a_1+a_9,a_2+a_{10},\ldots).$$
Quite generally, this shows that $$\rho^{2^p}(a_1,a_2,a_3,\ldots)
\sim (a_1+a_{1+2^p},a_2+a_{2+2^p},a_3+a_{3+2^p},\ldots).$$ Now
suppose that the original sequence $(a_1,a_2,\ldots)$ is periodic
with period $2^m$. Then $a_j=a_{j+2^m}$ for all $j$, so that
$$\rho^{2^m}(a_1,a_2,a_3,\ldots) \sim (2a_1,2a_2,2a_3,\ldots)\sim
(0,0,0,\ldots).$$ Clearly this implies that
$\theta^{2^m}(a_1,\ldots,a_{2^m})$ has all components even,
and the lemma (and hence the theorem) is proved.
References
(1) Ciamberlini, C. and Maregoni, A., Su una interessante
curiosit\`a numerica, {\sl Period. Mat. Ser. 4} 17 (1937),
25-30.
(2) Honsberger, R., {\sl Ingenuity in Mathematics}, Random
House, New York, 1970.
(3) Lotan, M., A problem in difference sets, {\sl Amer. Math.
Monthly} 56 (1949), 535-541.
(4) Miller, R., A game with $n$ numbers, {\sl Amer. Math. Monthly}
85 (1978), 183-185.
(5) Zvengrowski, P., Iterated absolute differences, {\sl Math.
Mag.} 52 (1979), 36-37.