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
[1] P. Erdos, On the distribution function of additive functions, Ann. of Math., 47(1946), 1-20
[2] E. Howe, A new proof of Erdos’s theorem on monotone multiplicative functions, Amer. Math. Monthly, 93(1986), 593-595
[3] 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.

1. 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. 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.