# Solution to puzzle 42: Multiplicative sequence

Let {an} be a strictly increasing sequence of positive integers such that:

• a2 = 2
• amn = aman for m, n relatively prime (multiplicative property)

Show that an = n, for every positive integer, n.

We will first show that a3 = 3.

 Consider a3a5 = a15  (multiplicative property) < a18  (strictly increasing property) = a2a9  (multiplicative property) = 2a9  (a2 = 2) < 2a10  (strictly increasing property) = 2a2a5  (multiplicative property) = 4a5  (a2 = 2)

Hence a3a5 < 4a5, and so a3 < 4.  (Since a5 > 0.)
We also have 2 = a2 < a3.
Therefore a3 = 3.

Now consider a6 = a2a3 = 6.
Since the sequence is strictly increasing, we have only two slots for a4 and a5.
Hence a4 = 4, a5 = 5.

Then consider a10 = a2a5 = 10.
We conclude, similarly, that an = n, for 5 < n < 10.

Clearly we can continue this process, a form of mathematical induction, indefinitely.

Given an odd number, 2k + 1 > 1, for which a2k+1 = 2k + 1, we have a2(2k+1) = a2a2k+1 = 2(2k + 1).
We then have 2k slots for 2k elements, forcing an = n, for 2k + 1 < n < 2(2k + 1).
In particular, since k > 0, we have a2(k+1)+1 = 2(k + 1) + 1, which completes the induction step.

Finally, since {an} is a sequence of positive integers, a1 < a2 allows us to conclude that a1 = 1.
Therefore an = n, for every positive integer, n.

Source: Problem of the Week 967 on The Math Forum @ Drexel