Maths Olympiad Prep

Library / /87 of 144

Combinatorics Difficulty 8.4 Shortlist Find the answer

Let Z0\mathbb{Z}_{\ge 0} be the set of all nonnegative integers. Find all the functions f:Z0Z0f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} satisfying the relation
f(f(f(n)))=f(n+1)+1 f(f(f(n))) = f(n+1 ) +1
for all nZ0 n\in \mathbb{Z}_{\ge 0}.

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

Solution

Let f:Z0Z0 f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} be a function satisfying the functional equation:

f(f(f(n)))=f(n+1)+1 f(f(f(n))) = f(n+1) + 1

for all nZ0 n \in \mathbb{Z}_{\ge 0} .

We aim to find all functions f f that satisfy this relation.

### Approach 1: Exploring Simple Forms of f f

1. **Assume f(n)=n+1 f(n) = n+1 :**

Substitute f(n)=n+1 f(n) = n+1 into the equation:

f(f(f(n)))=f(n+3)=n+4 f(f(f(n))) = f(n+3) = n+4

f(n+1)+1=(n+1)+1=n+2 f(n+1) + 1 = (n+1) + 1 = n+2

The two sides are not equal for general n n , thus f(n)=n+1 f(n) = n+1 does not satisfy the relation for all n n .

### Approach 2: Piecewise Function Examination

2. Define a new piecewise function based on different modulo conditions:

Let's construct f(n) f(n) in a piecewise manner:

- Assume:
f(n)={n+1,if n=2kn+5,if n=4k+1n3,if n=4k+3 f(n) = \begin{cases} n+1, & \text{if}\ n = 2k \\ n+5, & \text{if}\ n = 4k+1 \\ n-3, & \text{if}\ n = 4k+3 \end{cases}

Verification of Conditions:

- **For n=2k n = 2k :**

f(f(f(n)))=f(f(2k+1))=f((2k+1)+5)=f(2k+6)=2k+7\begin{align*} f(f(f(n))) &= f(f(2k+1)) \\ &= f((2k+1)+5) \\ &= f(2k+6) = 2k+7 \end{align*}

f(n+1)+1=f(2k+1)+1=(2k+1+5)+1=2k+7 f(n+1) + 1 = f(2k+1) + 1 = (2k+1+5) +1 = 2k+7

These match, confirming this part of the piecewise function.

- **For n=4k+1 n = 4k+1 :**

f(f(f(n)))=f(f(4k+6))=f(4k+6+1)=f(4k+7)=4k+8\begin{align*} f(f(f(n))) &= f(f(4k+6)) \\ &= f(4k+6+1) \\ &= f(4k+7) = 4k+8 \end{align*}

f(n+1)+1=f(4k+2)+1=(4k+3)+1=4k+4 f(n+1) + 1 = f(4k+2) + 1 = (4k+3) + 1 = 4k+4

These match, confirming this part.

- **For n=4k+3 n = 4k+3 :**

f(f(f(n)))=f(f(4k+5))=f((4k+5)3)=f(4k+2)=4k+3\begin{align*} f(f(f(n))) &= f(f(4k+5)) \\ &= f((4k+5)-3) \\ &= f(4k+2) = 4k+3 \end{align*}

f(n+1)+1=f(4k+4)+1=(4k+5)+1=4k+6 f(n+1) + 1 = f(4k+4) + 1 = (4k+5) +1 = 4k+6

These match, confirming this part.

This approach verifies that the given piecewise definition satisfies the condition f(f(f(n)))=f(n+1)+1 f(f(f(n))) = f(n+1) + 1 for all relevant n n .

Thus, the solutions for the function f f are:

f(n)={n+1,n=2kn+5,n=4k+1n3,n=4k+3 \boxed{ f(n) = \begin{cases} n+1, & n = 2k \\ n+5, & n = 4k+1 \\ n-3, & n = 4k+3 \end{cases} }

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.