Let N be the set of natural numbers. Suppose \( f : N \to N \) is a function satisfying the following conditions:

(a) f(mn) = f(m)f(n)

(b) f(m) < f(n) if m < n

(c) f(2) = 2

What is the value of \( \displaystyle {\sum_{k=1}^{20} f(k)} \)

PRMO (Pre Regional Math Olympiad) 2012, India. Problem 16

Functional Equation

3 out of 10

Functional Equations by Venkatchala

Do you really need a hint? Try it first!

The first property is known as **multiplicative property. **The second one is known as **monotonic. **

**Strategy 0**

Find some values of f(x) for some x. This may yield a pattern.

__________

Notice that f(2) = 2 is given.

Can you find out f(1) (using the multiplicative property)?

Consider the following:

$$ f(2) = f(1 \times 2 ) = f(1) \times f(2) $$

Hence we have \(2 = f(1) \times 2 \)

Thus f(1) = 1

Can you find out f(4), f(8) and f(16) in a similar manner?

Clearly the following strategy works : \( f(4) = f(2\times 2) = f(2) \times f(20 = 2 \times 2 = 4 \)

Similarly f(8) = 8 and f(16) = 16.

Can you find out f(3) and generalize a strategy to find f(n)?

We use the monotonic property.

f(2) < f(3) < f(4)

But that means 2 < f(3) < 4. There is exactly one integer between 2 and 4. That is 3. Hence f(3) = 3.

Now use induction to show f(n) = n for any natural number n. Here is a summary of the argument.

- Assume f(k) = k for all integers less than n> 4
- If k+1 is composite then f(k+1) = k+1 (write k+1 as a product of factors r and s both greater than 1. By inductive hypothesis, we know f(r) = r and f(s) = s, therefore f(k+1) = f(rs) = f(r)f(s) = rs = k+1
- If k+1 is prime then k+2 must be composite (as n > 4 there are no consecutive prime numbers). and k+2 can be written as product of numbers r and s greater than 1 and less than k+1. Thus using the above strategy f(k+2) = k+2
- Finally f(k+1) = k+1 by monotonic property.

Since f(n) = n, f(1) + … + f(20) = 1+ … + 20 = 210

Math Olympiad is the greatest and most challenging academic contest for school students. Brilliant school students from over 100 countries participate in it every year.

Cheenta works with small groups of gifted students through an intense training program. It is a deeply personalized journey toward intellectual prowess and technical sophistication.