Maths Olympiad Prep

Library / /39 of 106

Algebra Difficulty 8.2 Shortlist Find the answer

Let N={1,2,3,}\mathbb{N} = \{1,2,3, \ldots\}. Determine if there exists a strictly increasing function f:NNf: \mathbb{N} \mapsto \mathbb{N} with the following properties:

(i) f(1)=2f(1) = 2;

(ii) f(f(n))=f(n)+n,(nN)f(f(n)) = f(n) + n, (n \in \mathbb{N}).

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine if there exists a strictly increasing function f:NN f: \mathbb{N} \to \mathbb{N} that satisfies the given properties, we need to construct such a function and verify its properties:

Given:
1. f(1)=2 f(1) = 2 .
2. f(f(n))=f(n)+n f(f(n)) = f(n) + n for all nN n \in \mathbb{N} .

We aim to construct f f explicitly and show it satisfies all conditions, including strict monotonicity.

### Step-by-Step Construction

1. Evaluating the first few terms:

- From the condition (i), we know f(1)=2 f(1) = 2 .

2. Using condition (ii):

- Set n=1 n = 1 :
f(f(1))=f(1)+1=2+1=3 f(f(1)) = f(1) + 1 = 2 + 1 = 3
So, f(2)=3 f(2) = 3 .

- Set n=2 n = 2 :
f(f(2))=f(2)+2=3+2=5 f(f(2)) = f(2) + 2 = 3 + 2 = 5
So, f(3)=5 f(3) = 5 .

- Set n=3 n = 3 :
f(f(3))=f(3)+3=5+3=8 f(f(3)) = f(3) + 3 = 5 + 3 = 8
So, f(5)=8 f(5) = 8 .

3. Continuing this process, we generalize:

From this process, observe a pattern emerging and verify:

- Define f(n) f(n) such that it is strictly increasing, accounting for all n n using previous values recursively. For example:
- For objection f(f(n))=f(n)+n f(f(n)) = f(n) + n to hold, sums such as f(n+2)=f(n+1)+n f(n + 2) = f(n+1) + n fit, given prior f f values.

4. Monotonicity:

- Prove each step maintains strict monotonicity:
f(n)<f(n+1)by the structure presented, since we define each recursively adding positive integers. f(n) < f(n+1) \quad \text{by the structure presented, since we define each recursively adding positive integers.}

By this recursive building based on conditions given, a strictly increasing structure for f f does indeed emerge that supports all conditions f(1)=2 f(1)=2 and f(f(n))=f(n)+n f(f(n))=f(n)+n .

### Conclusion

Thus, a strictly increasing function f f satisfying all conditions can be constructed. Therefore, the answer to whether such a function exists is:
yes \boxed{\text{yes}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.