Integer 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

Integer Functional Equation

G H J

Reveal topic tags

functional equation

L

G H BBookmark kLocked kLocked NReply

Source: LMAO P1

The post below has been deleted. Click to close.

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

1051 posts

#1 h Sep 11, 2020, 11:52 PM • 1 Y

Y by brain_idea

Let $f\colon\mathbb{N} \to \mathbb{N}$ be a function that satisfies $\frac{ab}{f(a)} + \frac{ab}{f(b)} = f(a+b)$ for all positive integer pairs $(a,b).$ Find all possible functions $f.$

(Here, we define $\mathbb{N}$ as the set of all positive integers.)

Z K Y

The post below has been deleted. Click to close.

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

930 posts

#2 h Sep 12, 2020, 12:04 AM • 3 Y

Y by teomihai, SatisfiedMagma, Mango247

Let's write with $P(a,b)$ initial condition. Taking $P(1,1)$ we have $f(1)f(2)=2$ hence either $f(1)=2$ and $f(2)=1$ or $f(1)=1$ and $f(2)=2$ .

Case 1. $f(1)=2$ and $f(2)=1$ .

Taking $P(1,2)$ we get $f(3)=3$ . Taking $P(1,3)$ we get $f(4)=2.5$ a contradiction.

Case 2. $f(1)=1$ and $f(2)=2$ .

We prove via induction $f(n)=n$ for all positive integers $n$ . Clearly it is true for $n=1,2$ . Suppose that it is true for $n=k\geq 2$ then taking $P(k,1)$ we have $f(k+1)=\frac{k}{f(1)}+\frac{k}{f(k)}=\frac{k}{1}+\frac{k}{k}=k+1$ as desired.

This post has been edited 2 times. Last edited by dangerousliri, Sep 12, 2020, 12:32 AM

Z K Y

The post below has been deleted. Click to close.

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

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#3 h Sep 13, 2022, 7:55 AM

Y by

If $f(1)\neq 1$ then setting $a=b=1$ implies $f(2)=1.$ Then $f(3)=3$ but $f(4)\notin \mathbb N$ , impossible. So $f(1)=1$ and upon iteration, $f\equiv \text{Id}$ ; which works.

Z K Y

The post below has been deleted. Click to close.

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

834 posts

#4 h Sep 13, 2022, 9:00 AM

Y by

Plug in $(a,b)=(1,1)$ to get that $2=f(1)f(2).$

If $f(1)=1,$ we can know $b+\frac{b}{f(b)}=f(b+1),$ so $b\frac{f(b)+1}{f(b)}=f(b+1).$ $b=1$ gives the value of $f(2),$ $b=2$ gives the value of $f(3),$ thus all $f(x)$ is uniquely determined. In fact, $f(x)=x$ works since $b+a=a+b,$ and also in this case $f(1)=1,$ thus the only solution in this case if $f(x)=x.$

If $f(1)=2,$ we know $\frac{b}{2}+\frac{b}{f(b)}=f(b+1).$ We also know $f(2)=1,$ so plugging $b=2$ gives $f(3)=3.$ However, we now have $f(4)=\frac{5}{2},$ contradicting the assumption.

The answer is $f(x)=x.$

Z K Y

The post below has been deleted. Click to close.

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

10 posts

#5 h Sep 14, 2022, 6:13 AM

Y by

Let P(a,b) be the given assertion.
From P(1,1) , then f(2)f(1)=2 such that (f(1),f(2))=(1,2) or (2,1) .
If f(1)=2 ,f(2)=1. From P(1,2) and P(1,3) we will have f(3)=3 and f(4)=5/2 ∉ N. No solution.
If f(1)=1 ,f(2)=2. By choosing P(1,n) ,∀n ∈ N then n + (n/f(n)) = f(n+1) , and by using induction step, we will get f(n)=n, ∀n ∈ N
It is easy to check that f(n)=n, ∀n ∈ N satisfies the condition.

Z K Y

The post below has been deleted. Click to close.

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

11288 posts

#6 h Apr 30, 2025, 2:54 AM

Y by

mathlogician wrote:

Let $f\colon\mathbb{N} \to \mathbb{N}$ be a function that satisfies $\frac{ab}{f(a)} + \frac{ab}{f(b)} = f(a+b)$ for all positive integer pairs $(a,b).$ Find all possible functions $f.$

(Here, we define $\mathbb{N}$ as the set of all positive integers.)

Let $P(a,b)$ be the assertion $\frac{ab}{f(a)}+\frac{ab}{f(b)}=f(a+b)$ .

$P(1,1)\Rightarrow f(1)f(2)=2\Rightarrow f(1)\in\{1,2\}$
If $f(1)=2$ , then:
$P(2,1)\Rightarrow f(3)=3$
$P(3,1)\Rightarrow f(4)=\frac52$ , a contradiction.
So $f(1)=1$ .

$P(x,1)\Rightarrow f(x+1)=\frac x{f(x)}+x$ , by simple induction now we get $\boxed{f(x)=x}$ for all $x\in\mathbb N$ , which fits. ..

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a