Pretty hard functional equation

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Pretty hard functional equation

G H J

Reveal topic tags

functional equation

functional equation in Z

L

G H BBookmark kLocked kLocked NReply

Source: National MO, 9th grade

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

548 posts

vralex

#1 h Apr 29, 2020, 2:30 PM

Y by

Find all injective functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$ so that for every $n$ in $\mathbb{Z} , f (f (n))-f(n)-1=0$ .

This post has been edited 4 times. Last edited by vralex, May 18, 2020, 9:22 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

548 posts

vralex

#2 h Apr 29, 2020, 2:32 PM

Y by

I believe we should prove that for every n f(n)=n+1. We do know this for every n in the image of f, so we may use that.
Any clue?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23515 posts

pco

#3 h Apr 29, 2020, 3:30 PM • 2 Y

Y by vralex, pagol

vralex wrote:

Find all injective functions of f:Z->Z so that for every n in Z, f (f (n))-f(n)-1=0.

We have $f(f(n))=f(n)+1$ $\forall n\in\mathbb Z$
And so $f(n)=n+1$ $\forall n\in f(\mathbb Z)$

If $a\in f(Z)$ , then $a+1\inf(\mathbb Z)$ and so two cases :

1) $f(\mathbb Z)=\mathbb Z$
And so $\boxed{f(x)=x+1\quad\forall x\in\mathbb Z}$
Which indeed is a solution

2) $f(\mathbb Z)=[n_0,+\infty)$ for some integer $n_0$
Then $f(n)=n+1$ $\forall n\ge n_0$
If $f(n_0-1)\ge n_0+1$ then $f(n_0-1)-1\in f(\mathbb Z)$ and so $f(f(n_0-1)-1)=f(n_0-1)$ and injectivity would imply $f(n_0-1)=n_0$ , contradiction
So $f(n_0-1)=n_0$
But then, same method gives $f(n_0-2)=n_0$ too, impossible since injective

And so no other solution in this part of the proof.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

144 posts

#4 h Apr 29, 2020, 4:24 PM • 1 Y

Y by vralex

pco wrote:

If $a\in f(Z)$ , then $a+1\in f(\mathbb Z)$

I believe this is what its supposed to be, right ?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

23515 posts

pco

#5 h Apr 29, 2020, 4:46 PM • 1 Y

Y by vralex

Indeed, missing space : "\inf(\mathbb Z) " $\to$ "\in f(\mathbb Z) "
Thanks

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

11344 posts

#6 h Apr 24, 2025, 6:01 AM

Y by

vralex wrote:

Find all injective functions $f:\mathbb{Z} \rightarrow \mathbb{Z}$ so that for every $n$ in $\mathbb{Z} , f (f (n))-f(n)-1=0$ .

nice

Note that if $f(a)=a+1$ for some $a\in\mathbb Z$ then $f(n)=n+1$ for all $n\ge a$ . The proof is that if $f(a)=a+1$ then $f(a+1)=f(f(a))=f(a)+1=a+2$ , so we get this result inductively.

Now the original equation implies $f(n)=n+1$ for all $n\in f(\mathbb Z)$ . If $f$ is unbounded below, then $\boxed{f(n)=n+1}$ for all $n$ because of the above result. Otherwise, let $s=\min(f(\mathbb Z))$ , we have $f(n)=n+1$ for $n\ge s$

Consider an arbitrary $n<s$ . We must have $f(n)\ge s$ (because of how $s$ is defined). However, if $f(n)>s$ we have $f(n)-1\ge s$ and so::
$f(f(n)-1)=(f(n)-1)+1=f(n)\Rightarrow f(n)=n+1$ by injectivity, so $n+1=f(n)>s$ which is impossible since $n<s$ . Therefore $f(n)=s$ for all $n<s$ which contradicts injectivity, hence no more solutions.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a