Solution to puzzle 42: Multiplicative sequence

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

a₂ = 2
a_mn = a_ma_n for m, n relatively prime (multiplicative property)

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

We will first show that a₃ = 3.

Consider a₃a₅	= a₁₅ (multiplicative property)
	< a₁₈ (strictly increasing property)
	= a₂a₉ (multiplicative property)
	= 2a₉ (a₂ = 2)
	< 2a₁₀ (strictly increasing property)
	= 2a₂a₅ (multiplicative property)
	= 4a₅ (a₂ = 2)

Hence a₃a₅ < 4a₅, and so a₃ < 4. (Since a₅ > 0.)
We also have 2 = a₂ < a₃.
Therefore a₃ = 3.

Now consider a₆ = a₂a₃ = 6.
Since the sequence is strictly increasing, we have only two slots for a₄ and a₅.
Hence a₄ = 4, a₅ = 5.

Then consider a₁₀ = a₂a₅ = 10.
We conclude, similarly, that a_n = 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 a_2k+1 = 2k + 1, we have a_2(2k+1) = a₂a_2k+1 = 2(2k + 1).
We then have 2k slots for 2k elements, forcing a_n = n, for 2k + 1 < n < 2(2k + 1).
In particular, since k > 0, we have a_2(k+1)+1 = 2(k + 1) + 1, which completes the induction step.

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

Solution to puzzle 42: Multiplicative sequence

Further reading