Feeds:
Posts

## S01 Increasing multiplicative functions

01a. PEN K12 (Canada 1969) Find all functions $f:\mathbb{N} \to \mathbb{N}$ such that for all $m, \, n\in \mathbb{N}$: $f(2) = 2$, $f(mn) = f(m)f(n)$, $f(n + 1) > f(n)$.

01b. Let $f:\mathbb{N} \to \mathbb{R}^{+}$ be a function satisfying the conditions:
(a) $f(mn) = f(m)f(n)$ for all relatively prime $m$ and $n$, and
(b) $f(n+1) \geq f(n)$ for all positive integers $n$.
Show that there is a constant $\alpha \in \mathbb{R}$ such that $f(n)=n^{\alpha}$ for all $n \in \mathbb{N}$.

Here is the official solution: PEN01S
An alternative solution is here: CMO 2003 (problem 4)
You can also disscuss the problems here!

References
 P. Erdos, On the distribution function of additive functions, Ann. of Math., 47(1946), 1-20
 E. Howe, A new proof of Erdos’s theorem on monotone multiplicative functions, Amer. Math. Monthly, 93(1986), 593-595
 L. Moser and J. Lambek, On monotone multiplicative functions, Proc. Amer. Math. Soc., 4(1953), 544-545

Acknowledgement. We would like to express our gratitude to Andrei Frimu who helped us preparing the solutions and Orlando Doehring who offered me the solution file of CMO 2003.

### 2 Responses

1. on June 11, 2008 at 4:30 am | Reply Johan

I guess the first solution for 01a is not valid. How do you prove that $f(x)=x$ is the only solution? The induction steps prove that the function works, but they don’t prove that no other function works as well.

2. on June 14, 2008 at 9:30 am | Reply aimingbeyond

The solution is valid. The induction step does not simply prove that $f(n+1)=n+1$ works, but that $n+1$ is the only possible value $f(n+1)$ can take.