# Solution to puzzle 42: Multiplicative sequence

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

- a
_{2} = 2 - a
_{mn} = a_{m}a_{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} = 3.

Consider a_{3}a_{5} | = a_{15} (multiplicative property) |

| < a_{18} (strictly increasing property) |

| = a_{2}a_{9} (multiplicative property) |

| = 2a_{9} (a_{2} = 2) |

| < 2a_{10} (strictly increasing property) |

| = 2a_{2}a_{5} (multiplicative property) |

| = 4a_{5} (a_{2} = 2) |

Hence a_{3}a_{5} < 4a_{5}, and so a_{3} < 4. (Since a_{5} > 0.)

We also have 2 = a_{2} < a_{3}.

Therefore a_{3} = 3.

Now consider a_{6} = a_{2}a_{3} = 6.

Since the sequence is strictly increasing, we have only two slots for a_{4} and a_{5}.

Hence a_{4} = 4, a_{5} = 5.

Then consider a_{10} = a_{2}a_{5} = 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_{2}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_{1} < a_{2} allows us to conclude that a_{1} = 1.

Therefore a_{n} = n, for every positive integer, n.

## Further reading

- Multiplicative Function
- An Unusual Multiplicative Function

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

Back to top